{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T15:59:56Z","timestamp":1774367996783,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642325885","type":"print"},{"value":"9783642325892","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_43","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T08:44:32Z","timestamp":1343810672000},"page":"478-490","source":"Crossref","is-referenced-by-count":2,"title":["Planarizing Gadgets for Perfect Matching Do Not Exist"],"prefix":"10.1007","author":[{"given":"Rohit","family":"Gurjar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arpita","family":"Korwar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jochen","family":"Messner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon","family":"Straub","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M.: On derandomizing tests for certain polynomial identities. In: Proceedings of the Conference on Computational Complexity, pp. 355\u2013359 (2003)","DOI":"10.1109\/CCC.2003.1214434"},{"key":"43_CR2","unstructured":"Burke, K.: http:\/\/cstheory.stackexchange.com\/questions\/9587 (2012)"},{"key":"43_CR3","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jagm.1993.1046","volume":"15","author":"E. Dahlhaus","year":"1993","unstructured":"Dahlhaus, E., Hajnal, P., Karpinski, M.: On the parallel complexity of Hamiltonian cycles and matching problem in dense graphs. J. Algorithms\u00a015, 367\u2013384 (1993)","journal-title":"J. Algorithms"},{"key":"43_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0166-218X(98)00006-7","volume":"84","author":"E. Dahlhaus","year":"1998","unstructured":"Dahlhaus, E., Karpinski, M.: Matching and multidimensional matching in chordal and strongly chordal graphs. Disc. Appl. Math.\u00a084, 79\u201391 (1998)","journal-title":"Disc. Appl. Math."},{"key":"43_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1714450.1714453","volume":"10","author":"S. Datta","year":"2010","unstructured":"Datta, S., Kulkarni, R., Limaye, N., Mahajan, M.: Planarity, determinants, permanents, and (unique) matchings. ACM Trans. Comput. Theory, 10:1\u201310:20 (2010)","journal-title":"ACM Trans. Comput. Theory"},{"key":"43_CR6","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s00224-009-9204-8","volume":"47","author":"S. Datta","year":"2010","unstructured":"Datta, S., Kulkarni, R., Roy, S.: Deterministically isolating a perfect matching in bipartite planar graphs. Theor. Comput. Syst.\u00a047, 737\u2013757 (2010)","journal-title":"Theor. Comput. Syst."},{"key":"43_CR7","unstructured":"Datta, S., Kulkarni, R., Tewari, R.: Perfect matching in bipartite planar graphs is in UL. Technical Report TR10-201, ECCC (2011)"},{"key":"43_CR8","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. Can. J. Math.\u00a017, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"2","key":"43_CR9","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/jagm.2001.1167","volume":"40","author":"H.N. Gabow","year":"2001","unstructured":"Gabow, H.N., Kaplan, H., Tarjan, R.E.: Unique maximum matching algorithms. J. Algorithms\u00a040(2), 159\u2013183 (2001)","journal-title":"J. Algorithms"},{"issue":"3","key":"43_CR10","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor.\u00a0Comput.\u00a0Sci.\u00a01(3), 237\u2013267 (1976)","journal-title":"Theor.\u00a0Comput.\u00a0Sci."},{"issue":"4","key":"43_CR11","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput\u00a05(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput"},{"key":"43_CR12","unstructured":"Gasarch, W.: Is there a nice gadget for showing planar HC is NPC? Computational Complexity Blog (2012), http:\/\/blog.computationalcomplexity.org\/2012\/01\/is-there-nice-gadget-for-showing-planar.html"},{"key":"43_CR13","doi-asserted-by":"crossref","unstructured":"Hoang, T.M.: On the matching problem for special graph classes. In: Proceedings of the Conference on Computational Complexity, pp. 139\u2013150 (2010)","DOI":"10.1109\/CCC.2010.21"},{"key":"43_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/11786986_40","volume-title":"Automata, Languages and Programming","author":"T.M. Hoang","year":"2006","unstructured":"Hoang, T.M., Mahajan, M., Thierauf, T.: On the Bipartite Unique Perfect Matching Problem. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 453\u2013464. Springer, Heidelberg (2006)"},{"key":"43_CR15","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"Hopcroft, J., Karp, R.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput.\u00a02, 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"43_CR16","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Rytter, W.: Fast Parallel Algorithms for Graph Matching Problems. Oxford University Press (1998)","DOI":"10.1093\/oso\/9780198501626.001.0001"},{"key":"43_CR17","unstructured":"Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoret. Physics, pp. 43\u2013110. Academic Press (1967)"},{"key":"43_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1007\/3-540-16042-6_28","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"D.C. Kozen","year":"1985","unstructured":"Kozen, D.C., Vazirani, U.V., Vazirani, V.V.: NC Algorithms for Comparability Graphs, Interval Graphs, and Testing for Unique Perfect Matchings. In: Maheshwari, S.N. (ed.) FSTTCS 1985. LNCS, vol.\u00a0206, pp. 496\u2013503. Springer, Heidelberg (1985)"},{"key":"43_CR19","doi-asserted-by":"crossref","unstructured":"Kozen, D.: The Design and Analysis of Algorithms. Springer (1991)","DOI":"10.1007\/978-1-4612-4400-4"},{"key":"43_CR20","unstructured":"Kulkarni, R., Mahajan, M., Varadarajan, K.: Some perfect matchings and perfect half-integral matchings in NC. Chic. J. Theor. Comput.\u00a02008(4) (2008)"},{"key":"43_CR21","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","volume":"30","author":"G. Lev","year":"1981","unstructured":"Lev, G., Pippenger, M., Valiant, L.: A fast parallel algorithm for routing in permutation networks. IEEE Trans. Computers\u00a030, 93\u2013100 (1981)","journal-title":"IEEE Trans. Computers"},{"key":"43_CR22","unstructured":"Lovasz, L., Plummer, M.D.: Matching theory. North-Holland (1986)"},{"key":"43_CR23","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Varadarajan, K.R.: A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs. In: 32th ACM Symp. Theo. Comput (STOC), pp. 351\u2013357. ACM Press (2000)","DOI":"10.1145\/335305.335346"},{"key":"43_CR24","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.: An ${O}(\\sqrt{|v|}\\cdot{|E|})$ algorithm for finding maximum matching in general graphs. In: FOCS, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"43_CR25","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G.L. Miller","year":"1995","unstructured":"Miller, G.L., Naor, J.S.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput.\u00a024, 1002\u20131017 (1995)","journal-title":"SIAM J. Comput."},{"key":"43_CR26","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U., Vazirani, V.: Matching is as easy as matrix inversion. Combinatorica\u00a07, 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"43_CR27","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. J. ACM\u00a029, 285\u2013309 (1982)","journal-title":"J. ACM"},{"key":"43_CR28","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"43_CR29","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/0890-5401(89)90017-5","volume":"80","author":"V. Vazirani","year":"1989","unstructured":"Vazirani, V.: NC algorithms for computing the number of perfect matchings in K 3,3-free graphs and related problems. Inf. Comput.\u00a080, 152\u2013164 (1989)","journal-title":"Inf. Comput."},{"key":"43_CR30","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"V. Vazirani","year":"1994","unstructured":"Vazirani, V.: A theory of alternating paths and blossoms for proving correctness of the ${O}(\\sqrt{V}{E})$ general graph maximum matching algorithm. Combinatorica\u00a014, 71\u2013109 (1994)","journal-title":"Combinatorica"},{"issue":"1-2","key":"43_CR31","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s00453-011-9519-0","volume":"63","author":"R. Yuster","year":"2012","unstructured":"Yuster, R.: Almost exact matchings. Algorithmica\u00a063(1-2), 39\u201350 (2012)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T11:22:10Z","timestamp":1743938530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}