{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T12:40:24Z","timestamp":1739018424246,"version":"3.37.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,3,17]],"date-time":"2009-03-17T00:00:00Z","timestamp":1237248000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,10]]},"DOI":"10.1007\/s00224-009-9204-8","type":"journal-article","created":{"date-parts":[[2009,3,16]],"date-time":"2009-03-16T18:43:38Z","timestamp":1237229018000},"page":"737-757","source":"Crossref","is-referenced-by-count":20,"title":["Deterministically Isolating a Perfect Matching in\u00a0Bipartite Planar Graphs"],"prefix":"10.1007","volume":"47","author":[{"given":"Samir","family":"Datta","sequence":"first","affiliation":[]},{"given":"Raghav","family":"Kulkarni","sequence":"additional","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,3,17]]},"reference":[{"key":"9204_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E., Barrington, D.A.M., Chakraborty, T., Datta, S., Roy, S.: Grid graph reachability problems. In: IEEE Conference on Computational Complexity, pp. 299\u2013313 (2006)","DOI":"10.1109\/CCC.2006.22"},{"key":"9204_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Datta, S., Roy, S.: The directed planar reachability problem. In: FSTTCS, pp. 238\u2013249 (2005)","DOI":"10.1007\/11590156_19"},{"issue":"2","key":"9204_CR3","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1006\/jcss.1999.1646","volume":"59","author":"E. Allender","year":"1999","unstructured":"Allender, E., Reinhardt, K., Zhou, S.: Isolation, matching, and counting: uniform and nonuniform upper bounds. J. Comput. Syst. Sci. 59(2), 164\u2013181 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9204_CR4","doi-asserted-by":"crossref","unstructured":"Braverman, M., Kulkarni, R., Roy, S.: Parity problems in planar graphs. In: IEEE Conference on Computational Complexity, pp. 222\u2013235 (2007)","DOI":"10.1109\/CCC.2007.23"},{"key":"9204_CR5","doi-asserted-by":"crossref","unstructured":"Bourke, C., Tewari, R., Vinodchandran, N.V.: Directed planar reachability is in unambiguous log-space. In: IEEE Conference on Computational Complexity, pp. 217\u2013221 (2007)","DOI":"10.1109\/CCC.2007.9"},{"key":"9204_CR6","doi-asserted-by":"crossref","unstructured":"Datta, S., Kulkarni, R., Limaye, N., Mahajan, M.: Planarity, determinants, permanents, and (unique) matchings. In: CSR, pp. 115\u2013126 (2007)","DOI":"10.1007\/978-3-540-74510-5_14"},{"key":"9204_CR7","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2005)"},{"key":"9204_CR8","first-page":"166","volume-title":"Proceedings of 28th IEEE Conference on Foundations of Computer Science","author":"D. Grigoriev","year":"1987","unstructured":"Grigoriev, D., Karpinski, M.: The matching problem for bipartite graphs with polynomially bounded permanent is in $\\mathsf{NC}$ . In: Proceedings of 28th IEEE Conference on Foundations of Computer Science, pp. 166\u2013172. IEEE Computer Society Press, Los Alamitos (1987)"},{"issue":"1\u20132","key":"9204_CR9","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1016\/S0304-3975(01)00108-6","volume":"270","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Theor. Comput. Sci. Arch. 270(1\u20132), 761\u2013777 (2002)","journal-title":"Theor. Comput. Sci. Arch."},{"key":"9204_CR10","first-page":"43","volume-title":"Graph Theory and Theoretical Physics","author":"P.W. Kasteleyn","year":"1967","unstructured":"Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp. 43\u2013110. Academic Press, New York (1967)"},{"key":"9204_CR11","doi-asserted-by":"crossref","unstructured":"Kenyon, R.W., Propp, J.G., Wilson, D.B.: Trees matchings. Electron. J. Comb. 7(1)","DOI":"10.37236\/1503"},{"key":"9204_CR12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R. Karp","year":"1986","unstructured":"Karp, R., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random $\\mathsf{NC}$ . Combinatorica 6, 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"9204_CR13","doi-asserted-by":"crossref","unstructured":"Kozen, D., Vazirani, U.V., Vazirani, V.V.: $\\mathsf{NC}$ algorithms for comparability graphs, interval graphs, and testing for unique perfect matching. In: FSTTCS, pp. 496\u2013503 (1985)","DOI":"10.1007\/3-540-16042-6_28"},{"key":"9204_CR14","volume-title":"Matching Theory","author":"L. Lovasz","year":"1986","unstructured":"Lovasz, L., Plummer, M.: Matching Theory. North-Holland, Amsterdam (1986)"},{"key":"9204_CR15","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G. Miller","year":"1995","unstructured":"Miller, G., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput. 24, 1002\u20131017 (1995)","journal-title":"SIAM J. Comput."},{"key":"9204_CR16","unstructured":"Mahajan, M., Vinay, V.: A combinatorial algorithm for the determinant. In: SODA, pp. 730\u2013738 (1997)"},{"key":"9204_CR17","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Varadarajan, K.: A new $\\mathsf{NC}$ algorithm to find a perfect matching in planar and bounded genus graphs. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 351\u2013357 (2000)","DOI":"10.1145\/335305.335346"},{"issue":"1","key":"9204_CR18","doi-asserted-by":"crossref","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 7(1), 105\u2013131 (1987)","journal-title":"Combinatorica"},{"key":"9204_CR19","doi-asserted-by":"crossref","unstructured":"Vazirani, V.: $\\mathsf{NC}$ algorithms for computing the number of perfect matchings in K 3,3-free graphs and related problems. In: SWAT, pp. 233\u2013242 (1988)","DOI":"10.1007\/3-540-19487-8_27"},{"key":"9204_CR20","series-title":"An EATCS Series","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity\u2014A Uniform Approach; Texts in Theoretical Computer Science","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity\u2014A Uniform Approach; Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (1999)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9204-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9204-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9204-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T12:20:51Z","timestamp":1739017251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9204-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,17]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9204"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9204-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2009,3,17]]}}}