{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T17:16:52Z","timestamp":1771262212539,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1987,3,1]],"date-time":"1987-03-01T00:00:00Z","timestamp":541555200000},"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":[[1987,3]]},"DOI":"10.1007\/bf02579206","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T21:14:06Z","timestamp":1174598046000},"page":"105-113","source":"Crossref","is-referenced-by-count":339,"title":["Matching is as easy as matrix inversion"],"prefix":"10.1007","volume":"7","author":[{"given":"Ketan","family":"Mulmuley","sequence":"first","affiliation":[]},{"given":"Umesh V.","family":"Vazirani","sequence":"additional","affiliation":[]},{"given":"Vijay V.","family":"Vazirani","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02579206_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook, A Taxonomy of Problems with Fast Parallel Algorithms,Information and Control,64 (1985), 2\u201322.","journal-title":"Information and Control"},{"key":"BF02579206_CR2","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/0205040","volume":"5","author":"L. Cs\u00e1nky","year":"1976","unstructured":"L. Cs\u00e1nky, Fast Parallel Matrix Inversion Algorithms.SIAM J. Computing,5 (1976), 618\u2013623.","journal-title":"SIAM J. Computing"},{"key":"BF02579206_CR3","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Paths, Trees and Flowers,Canad. J. Math.,17 (1965), 449\u2013467.","journal-title":"Canad. J. Math."},{"key":"BF02579206_CR4","doi-asserted-by":"crossref","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"4","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds, Systems of Distinct Representatives and Linear Algebra,J. Res. Nat. Bureau of Standards, 71B,4 (1967), 241\u2013245.","journal-title":"J. Res. Nat. Bureau of Standards, 71B"},{"key":"BF02579206_CR5","doi-asserted-by":"crossref","unstructured":"Z. Galil andV. Pan, Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC,Twenty Sixth Annual IEEE Symp. on the Foundations of Computer Science. (1985), 490\u2013495.","DOI":"10.1109\/SFCS.1985.33"},{"key":"BF02579206_CR6","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02579264","volume":"6","author":"H. Karloff","year":"1986","unstructured":"H. Karloff, A Randomized Parallel Algorithm for the Odd Set Cover Problem,Combinatorica 6 (1986), 387\u2013391.","journal-title":"Combinatorica"},{"key":"BF02579206_CR7","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal andA. Wigderson, Finding a Maximum Matching is in Random NC,Seventeenth Annual Symp. on Theory of Computing. (1985), 22\u201332.","DOI":"10.1145\/22145.22148"},{"key":"BF02579206_CR8","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal andA. Wigderson, Are Search and Decision Problems Computationally Equivalent?Seventeenth Annual Symp. on Theory of Computing. (1985).","DOI":"10.1145\/22145.22197"},{"key":"BF02579206_CR9","doi-asserted-by":"crossref","unstructured":"D. Kozen, U. V. Vazirani andV. V. Vazirani, NC Algorithms for Comparability Graphs, Interval graphs, and Testing for Unique Perfect Matching,Fifth Annual Foundations of Software Technology and Theoretical Computer Science Conference (1985), invited paper inTheoretical Computer Science.","DOI":"10.1007\/3-540-16042-6_28"},{"key":"BF02579206_CR10","volume-title":"Fundamentals of Computing Theory","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, On Determinants, Matchings and Random Algorithms,Fundamentals of Computing Theory, edited by L. Budach, Akademia-Verlag, Berlin, (1979)."},{"key":"BF02579206_CR11","volume-title":"Combinatorial Problems and Exercises","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz,Combinatorial Problems and Exercises, Akad\u00e9miai Kiad\u00f3, and North-Holland, Amsterdam, (1979)."},{"key":"BF02579206_CR12","volume-title":"Matcing Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"L. Lov\u00e1sz andM. Plummer,Matcing Theory, Academic Press, Budapest, Hungary, (1986)."},{"key":"BF02579206_CR13","doi-asserted-by":"crossref","unstructured":"S. Micali andV. V. Vazirani, AnO(\u221a|V||E|) Algorithm for Finding Maximum Matching in General Graphs,Twenty First Annual IEEE Symp. on the Foundations of Computer Science (1980), 17\u201327.","DOI":"10.1109\/SFCS.1980.12"},{"key":"BF02579206_CR14","doi-asserted-by":"crossref","unstructured":"V. Pan, Fast and Efficient Algorithms for the Exact Inversion of Integer Matrices,Fifth Annual Foundations of Software Technology and Theoretical Computer Science Conference (1985).","DOI":"10.1007\/3-540-16042-6_29"},{"key":"BF02579206_CR15","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"C. H. Papadimitriou","year":"1982","unstructured":"C. H. Papadimitriou andM. Yannakakis, The Complexity of Restricted Spanning Tree Problems,Journal of the ACM,29 (1982), 285\u2013309.","journal-title":"Journal of the ACM"},{"key":"BF02579206_CR16","unstructured":"M. O. Rabin andV. V. Vazirani, Maximum Matching in General Gaphs Through Randomization, submitted."},{"key":"BF02579206_CR17","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":"BF02579206_CR18","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W. T. Tutte","year":"1947","unstructured":"W. T. Tutte, The Factorization of Linear Graphs,J. London Math. Soc.,22 (1947), 107\u2013111.","journal-title":"J. London Math. Soc."},{"key":"BF02579206_CR19","doi-asserted-by":"crossref","unstructured":"L. G. Valiant andV. V. Vazirani, NP is as Easy as Detecting Unique Solutions,Seventeenth Annual Symp. on Theory of Computing. (1985), to appear inTheoretical Computer Science.","DOI":"10.1145\/22145.22196"},{"key":"BF02579206_CR20","doi-asserted-by":"crossref","unstructured":"U. V. Vazirani andV. V. Vazirani, The Two-Processor Scheduling Problem is in Random NC,Seventeenth Annual Symp. on Theory of Computing (1985), 11\u201321, submitted.","DOI":"10.1145\/22145.22147"},{"key":"BF02579206_CR21","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. Pippinger, Parallel Computation for Well-endowed Rings and Space Bounded ProbabilisticMachines, Information and Control,58 (1983) 113\u2013136.","journal-title":"Information and Control"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579206.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579206\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T05:05:26Z","timestamp":1736917526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,3]]}},"alternative-id":["BF02579206"],"URL":"https:\/\/doi.org\/10.1007\/bf02579206","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,3]]}}}