{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:47:15Z","timestamp":1725472035325},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540359043"},{"type":"electronic","value":"9783540359050"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_40","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T10:46:45Z","timestamp":1151491605000},"page":"453-464","source":"Crossref","is-referenced-by-count":10,"title":["On the Bipartite Unique Perfect Matching Problem"],"prefix":"10.1007","author":[{"given":"Thanh Minh","family":"Hoang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"40_CR1","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00224-003-1077-7","volume":"36","author":"E. Allender","year":"2003","unstructured":"Allender, E., Arvind, V., Mahajan, M.: Arithmetic complexity, Kleene closure, and formal power series. Theory Comput. Syst.\u00a036(4), 303\u2013328 (2003)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"40_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s000370050023","volume":"8","author":"E. Allender","year":"1999","unstructured":"Allender, E., Beals, R., Ogihara, M.: The complexity of matrix rank and feasible systems of linear equations. Computational Complexity\u00a08(2), 99\u2013126 (1999)","journal-title":"Computational Complexity"},{"key":"40_CR3","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a059, 164\u2013181 (1999)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"40_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"Chandra, A., Stockmeyer, L., Vishkin, U.: Constant depth reducibility. SIAM Journal on Computing\u00a013(2), 423\u2013439 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"40_CR5","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0-1 vertices. Journal of Research National Bureau of Standards\u00a069, 125\u2013130 (1965)","journal-title":"Journal of Research National Bureau of Standards"},{"key":"40_CR6","first-page":"70","volume-title":"31st Symposium on Theory of Computing (STOC)","author":"H.N. Gabow","year":"1999","unstructured":"Gabow, H.N., Kaplan, H., Tarjan, R.E.: Unique maximum matching algorithms. In: 31st Symposium on Theory of Computing (STOC), pp. 70\u201378. ACM Press, New York (1999)"},{"key":"40_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0304-3975(02)00404-8","volume":"295","author":"T.M. Hoang","year":"2003","unstructured":"Hoang, T.M., Thierauf, T.: The complexity of the characteristic and the minimal polynomial. Theoretical Computer Science\u00a0295, 205\u2013222 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"40_CR8","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM Journal on Computing\u00a017(5), 935\u2013938 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"40_CR9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R.M. Karp","year":"1986","unstructured":"Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica\u00a06, 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"40_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1007\/3-540-16042-6_28","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"D. Kozen","year":"1985","unstructured":"Kozen, D., Vazirani, U., Vazirani, V.: NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching. In: Maheshwari, S.N. (ed.) FSTTCS 1985. LNCS, vol.\u00a0206, pp. 496\u2013503. Springer, Heidelberg (1985)"},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Kozen, D., Vazirani, U., Vazirani, V.: NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching. Technical Report TR86-799, Cornell University (1986)","DOI":"10.1007\/3-540-16042-6_28"},{"key":"40_CR12","unstructured":"Lovasz, L.: On determinants, matchings and random algorithms. In: Budach, L. (ed.) Proceedings of Conference on Fundamentals of Computing Theory, pp. 565\u2013574. Akademia-Verlag (1979)"},{"issue":"1","key":"40_CR13","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(1), 105\u2013131 (1987)","journal-title":"Combinatorica"},{"issue":"4","key":"40_CR14","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/0196-6774(89)90005-9","volume":"10","author":"M. Rabin","year":"1989","unstructured":"Rabin, M., Vazirani, V.: Maximum matchings in general graphs through randomization. Journal of Algorithms\u00a010(4), 557\u2013567 (1989)","journal-title":"Journal of Algorithms"},{"key":"40_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"},{"issue":"3","key":"40_CR16","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Informatica\u00a026(3), 279\u2013284 (1988)","journal-title":"Acta Informatica"},{"issue":"8","key":"40_CR17","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1093\/bioinformatics\/14.8.691","volume":"14","author":"J.E. Tabaska","year":"1998","unstructured":"Tabaska, J.E., Cary, R.B., Gabow, H.N., Stormo, G.D.: An RNA folding method capable of identifying pseudoknots and base triples. Bioinformatics\u00a014(8), 691\u2013699 (1998)","journal-title":"Bioinformatics"},{"key":"40_CR18","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)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:19:50Z","timestamp":1619507990000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11786986_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}