{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T15:04:21Z","timestamp":1780067061836,"version":"3.54.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2006,5]]},"DOI":"10.1007\/s00453-005-1187-5","type":"journal-article","created":{"date-parts":[[2006,2,16]],"date-time":"2006-02-16T23:00:10Z","timestamp":1140130810000},"page":"3-20","source":"Crossref","is-referenced-by-count":34,"title":["Maximum matchings in planar graphs via gaussian elimination"],"prefix":"10.1007","volume":"45","author":[{"given":"Marcin","family":"Mucha","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"1187_CR1","first-page":"586","volume-title":"Proc. 17th ICALP, Volume 443 of LNCS","author":"N. Blum","year":"1990","unstructured":"Blum, N.: A new approach to maximum matching in general graphs. In:Proc. 17th ICALP, Volume 443 of LNCS, Springer-Verlag, Berlin, 1990, pp. 586\u2013597."},{"key":"1187_CR2","doi-asserted-by":"crossref","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.Math. Comp. 28 (1974), 231\u2013236.","journal-title":"Math. Comp."},{"key":"1187_CR3","first-page":"1","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, ACM Press, New York, 1987, pp. 1\u20136."},{"key":"1187_CR4","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers.Canad. J. Math. 17 (1965), 449\u2013467.","journal-title":"Canad. J. Math."},{"key":"1187_CR5","doi-asserted-by":"crossref","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 38 (1991), 815\u2013853.","journal-title":"J. ACM"},{"key":"1187_CR6","volume-title":"Graph Theory and Theoretical Physics","year":"1967","unstructured":"Harary, F., editor:Graph Theory and Theoretical Physics. Academic Press, New York, 1967."},{"key":"1187_CR7","unstructured":"Khaira, M.S., Miller, G.L., Sheffler, T.J.: Nested dissection: a survey, Technical Report CS-92-106, 1992."},{"key":"1187_CR8","doi-asserted-by":"crossref","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, ACM Press, New York, 1994, pp. 27\u201337."},{"key":"1187_CR9","doi-asserted-by":"crossref","DOI":"10.1515\/9783112342442","volume-title":"Einfuhrung in die Determinanten Theorie","author":"G. Kowalewski","year":"1909","unstructured":"Kowalewski, G.:Einfuhrung in die Determinanten Theorie. Leipzig Verlag von Veit & Co, Leipzig, 1909."},{"key":"1187_CR10","doi-asserted-by":"crossref","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. Numer. Anal. 16 (1979), 346\u2013358.","journal-title":"SIAM J. Numer. Anal."},{"key":"1187_CR11","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs.SIAM J. Appl. Math. 36 (1979), 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"1187_CR12","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem.SIAM J. Comput. 9 (1980), 615\u2013627.","journal-title":"SIAM J. Comput."},{"key":"1187_CR13","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, Akademie-Verlag, Berlin, 1979, pp. 565\u2013574."},{"key":"1187_CR14","unstructured":"Micali, S., Vazirani, V.V.: Ano(\u221a|V||e|) algorithm for finding maximum matching in general graphs. In:Proceedings of the Twenty-First Annual IEEE Symposium on Foundations of Computer Science, 1980, pp. 17\u201327."},{"key":"1187_CR15","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Naor, J.: Flow in planar graphs with multiple sources and sinks. In:Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 112\u2013117.","DOI":"10.1109\/SFCS.1989.63464"},{"key":"1187_CR16","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In:Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 248\u2013255.","DOI":"10.1109\/FOCS.2004.40"},{"key":"1187_CR17","doi-asserted-by":"crossref","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. 22 (1993), 1227\u20131250.","journal-title":"SIAM J. Comput."},{"key":"1187_CR18","doi-asserted-by":"crossref","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.J. Algorithms 10 (1989), 557\u2013567.","journal-title":"J. Algorithms"},{"key":"1187_CR19","doi-asserted-by":"crossref","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.J. ACM 27 (1980), 701\u2013717.","journal-title":"J. ACM"},{"key":"1187_CR20","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal.Numer. Math. 13 (1969), 354\u2013356.","journal-title":"Numer. Math."},{"key":"1187_CR21","doi-asserted-by":"crossref","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. 22 (1947), 107\u2013111.","journal-title":"J. London Math. Soc."},{"key":"1187_CR22","first-page":"258","volume-title":"Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"D.B. Wilson","year":"1997","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, Philadelphia, PA, 1997, pp. 258\u2013267."},{"key":"1187_CR23","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"International Symposium on Symbolic and Algebraic Computation, Volume 72 of LNCS","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In:International Symposium on Symbolic and Algebraic Computation, Volume 72 of LNCS, Springer-Verlag, Berlin, 1979, pp. 216\u2013226."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-005-1187-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-005-1187-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-005-1187-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T14:22:43Z","timestamp":1683382963000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-005-1187-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["1187"],"URL":"https:\/\/doi.org\/10.1007\/s00453-005-1187-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5]]}}}