{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T13:16:29Z","timestamp":1762521389921},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230250"},{"type":"electronic","value":"9783540301400"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30140-0_48","type":"book-chapter","created":{"date-parts":[[2010,9,19]],"date-time":"2010-09-19T01:31:13Z","timestamp":1284859873000},"page":"532-543","source":"Crossref","is-referenced-by-count":28,"title":["Maximum Matchings in Planar Graphs via Gaussian Elimination"],"prefix":"10.1007","author":[{"given":"Marcin","family":"Mucha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"48_CR1","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: 45th Annual IEEE Symposium on Foundations of Computer Science (2004) (accepted)","DOI":"10.1109\/FOCS.2004.40"},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Canadian Journal of Mathematics\u00a017, 449\u2013467 (1965)","journal-title":"Canadian Journal of Mathematics"},{"key":"48_CR3","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An o( $\\sqrt{|V||e|}$ ) algorithm for finding maximum matching in general graphs. In: Proceedings of the twenty first annual IEEE Symposium on Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"48_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1007\/BFb0032060","volume-title":"Automata, Languages and Programming","author":"N. Blum","year":"1990","unstructured":"Blum, N.: A new approach to maximum matching in general graphs. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol.\u00a0443, pp. 586\u2013597. Springer, Heidelberg (1990)"},{"key":"48_CR5","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM\u00a038, 815\u2013853 (1991)","journal-title":"J. ACM"},{"key":"48_CR6","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Naor, J.: Flow in planar graphs with multiple sources and sinks. In: Proc. 30th IEEE Symp. Foundations of Computer Science, pp. 112\u2013117 (1989)","DOI":"10.1109\/SFCS.1989.63464"},{"key":"48_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/195058.195092","volume-title":"Proceedings of the twenty-sixth annual ACM symposium on Theory of computing","author":"P. Klein","year":"1994","unstructured":"Klein, P., Rao, S., Rauch, M., Subramanian, S.: Faster shortest-path algorithms for planar graphs. In: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 27\u201337. ACM Press, New York (1994)"},{"key":"48_CR8","first-page":"565","volume-title":"Fundamentals of Computation Theory","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On determinants, matchings and random algorithms. In: Budach, L. (ed.) Fundamentals of Computation Theory, pp. 565\u2013574. Akademie-Verlag, Berlin (1979)"},{"key":"48_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/28395.28396","volume-title":"Proceedings of the nineteenth annual ACM conference on Theory of computing","author":"D. Coppersmith","year":"1987","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 1\u20136. ACM Press, New York (1987)"},{"key":"48_CR10","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik\u00a013, 354\u2013356 (1969)","journal-title":"Numerische Mathematik"},{"key":"48_CR11","unstructured":"Wilson, D.B.: Determinant algorithms for random planar structures. In: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, pp. 258\u2013267 (1997)"},{"key":"48_CR12","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W.T. Tutte","year":"1947","unstructured":"Tutte, W.T.: The factorization of linear graphs. J. London Math. Soc.\u00a022, 107\u2013111 (1947)","journal-title":"J. London Math. Soc."},{"key":"48_CR13","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/0196-6774(89)90005-9","volume":"10","author":"M.O. Rabin","year":"1989","unstructured":"Rabin, M.O., Vazirani, V.V.: Maximum matchings in general graphs through randomization. Journal of Algorithms\u00a010, 557\u2013567 (1989)","journal-title":"Journal of Algorithms"},{"key":"48_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"},{"key":"48_CR15","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. Schwartz","year":"1980","unstructured":"Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM\u00a027, 701\u2013717 (1980)","journal-title":"Journal of the ACM"},{"key":"48_CR16","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1090\/S0025-5718-1974-0331751-8","volume":"28","author":"J. Bunch","year":"1974","unstructured":"Bunch, J., Hopcroft, J.: Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation\u00a028, 231\u2013236 (1974)","journal-title":"Mathematics of Computation"},{"key":"48_CR17","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Applied Math., 177\u2013189 (1979)","DOI":"10.1137\/0136016"},{"key":"48_CR18","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.: Generalized nested dissection. SIAM J. Num. Anal.\u00a016, 346\u2013358 (1979)","journal-title":"SIAM J. Num. Anal."},{"key":"48_CR19","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1137\/0222073","volume":"22","author":"V.Y. Pan","year":"1993","unstructured":"Pan, V.Y., Reif, J.H.: Fast and efficient parallel solution of sparse linear systems. SIAM J. Comput.\u00a022, 1227\u20131250 (1993)","journal-title":"SIAM J. Comput."},{"key":"48_CR20","unstructured":"Khaira, M.S., Miller, G.L., Sheffler, T.J.: Nested dissection: A survey. Technical Report CS-92-106 (1992)"},{"key":"48_CR21","doi-asserted-by":"crossref","unstructured":"Kowalewski, G.: Einfuhrung in die Determinanten Theorie. Leipzig Verlag von Veit & Co. (1909)","DOI":"10.1515\/9783112342442"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30140-0_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,10]],"date-time":"2021-11-10T05:24:42Z","timestamp":1636521882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30140-0_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230250","9783540301400"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30140-0_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}