{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:06:55Z","timestamp":1775282815758,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1986,3,1]],"date-time":"1986-03-01T00:00:00Z","timestamp":510019200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1986,3]]},"DOI":"10.1007\/bf02579407","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T22:19:26Z","timestamp":1174601966000},"page":"35-48","source":"Crossref","is-referenced-by-count":173,"title":["Constructing a perfect matching is in random NC"],"prefix":"10.1007","volume":"6","author":[{"given":"R. M.","family":"Karp","sequence":"first","affiliation":[]},{"given":"E.","family":"Upfal","sequence":"additional","affiliation":[]},{"given":"A.","family":"Wigderson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02579407_CR1","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"D. Angluin andL. G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings.J. of Comp. Syst. Sci. 18 (1979), 155\u2013193.","journal-title":"J. of Comp. Syst. Sci."},{"key":"BF02579407_CR2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0019-9958(83)80060-6","volume":"58","author":"A. Borodin","year":"1983","unstructured":"A. Borodin, S. A. Cook andN. Pippenger, Parallel computation for well-endowed rings and space bounded probabilistic machines.Information and Control 58 (1983), 113\u2013136.","journal-title":"Information and Control"},{"key":"BF02579407_CR3","first-page":"65","volume":"23","author":"A. Borodin","year":"1982","unstructured":"A. Borodin, J. von zur Gathen andJ. Hopcroft, Fast parallel matrix and GCD computations.Proc. 23 STOC (1982), 65\u201371.","journal-title":"Proc."},{"key":"BF02579407_CR4","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1145\/358141.358144","volume":"26","author":"S. A. Cook","year":"1983","unstructured":"S. A. Cook, An overview of computation complexity.CACM 26 (1983), 400\u2013408.","journal-title":"CACM"},{"key":"BF02579407_CR5","doi-asserted-by":"crossref","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71A","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds, Systems of distinct representatives and linear algebra.J. of Res. Nat. Bureau of Standards,71 A (1967), 241\u2013245.","journal-title":"J. of Res. Nat. Bureau of Standards"},{"key":"BF02579407_CR6","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"J. Edmonds andR. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems.J. of ACM 19 (1972), 248\u2013264.","journal-title":"J. of ACM"},{"key":"BF02579407_CR7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","volume":"21","author":"L. M. Goldschlager","year":"1982","unstructured":"L. M. Goldschlager, R. A. Shaw andJ. Staples, The maximum flow problem is logspace complete for P.Theoretical Computer Science 21 (1982), 105\u2013111.","journal-title":"Theoretical Computer Science"},{"key":"BF02579407_CR8","unstructured":"H. J. Karloff, A Las Vegas RNC algorithm for maximum matchingCombinatorica, to appear."},{"key":"BF02579407_CR9","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal andA. Wigderson, Are search and decision problems computationally equivalent?STOC 1985.","DOI":"10.1145\/22145.22197"},{"key":"BF02579407_CR10","doi-asserted-by":"crossref","unstructured":"D. Kozen, U. V. Vazirani andV. V. Vazirani, The two-processors scheduling problem is in R-NC.STOC 1985.","DOI":"10.1145\/22145.22147"},{"key":"BF02579407_CR11","unstructured":"L. Lov\u00e1sz, Determinants, matchings and random algorithms,in: Fundamentals of Computation Theory, FCT\u201979. (ed. L. Budach), Akademie-Verlag Berlin 1979, pp 565\u2013574."},{"key":"BF02579407_CR12","unstructured":"M. O. Rabin andV. V. Vazirani, Maximum matchings in general graphs through randomization, TR-15-84,Harvard University Center for Research in Computing Technology, 1984."},{"key":"BF02579407_CR13","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities.J. of ACM,27 (1980), 701\u2013717.","journal-title":"J. of ACM"},{"key":"BF02579407_CR14","doi-asserted-by":"crossref","unstructured":"E. Shamir andE. Upfal,N-processors graphs distributively achieve perfect matching inO(log2 N) beats.Proceeding of the First ACM SIGACT-SIGMOD Symp. on Principles of Distributed Computing. Ottawa, 1982, 238\u2013241.","DOI":"10.1145\/800220.806702"},{"key":"BF02579407_CR15","doi-asserted-by":"crossref","first-page":"314","DOI":"10.4153\/CJM-1952-028-2","volume":"4","author":"W. T. Tutte","year":"1952","unstructured":"W. T. Tutte, The factors of graphs.Canad. J. Math. 4 (1952), 314\u2013328.","journal-title":"Canad. J. Math."},{"key":"BF02579407_CR16","unstructured":"D. J. A. Welsh,Matroid Theory. Academic Press (1976)."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579407.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579407\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:45:04Z","timestamp":1558197904000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,3]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1986,3]]}},"alternative-id":["BF02579407"],"URL":"https:\/\/doi.org\/10.1007\/bf02579407","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,3]]}}}