{"entities":{"Q1095658":{"pageid":1106410,"ns":120,"title":"Item:Q1095658","lastrevid":69826905,"modified":"2026-04-13T10:36:47Z","type":"item","id":"Q1095658","labels":{"en":{"language":"en","value":"Matching is as easy as matrix inversion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4028897"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$63250C3E-531F-4D32-8554-C11CE0F0F1F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ae6db7ab1d8cb65cdfcbab84b44f21dd19253b46","datavalue":{"value":{"text":"Matching is as easy as matrix inversion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095658$93EC104C-8A02-4070-AC22-AE550C83D75F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4ab039c00f282f4124d16445a87a2a4a9e3b2be4","datavalue":{"value":"0632.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$8E166843-F1F6-480E-9EAD-C6C60A57272A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dde64a11d0eda013b2f9a854fdaa4f704e32a39d","datavalue":{"value":"10.1007/BF02579206","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$63384531-BE6A-423A-A6E8-B8B72B88B995","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f12495924f470ae3671be11cd0c05f786ec14d07","datavalue":{"value":{"entity-type":"item","numeric-id":593776,"id":"Q593776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$C13B7A67-851B-4AF1-AC62-5320F6E143AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d60cc394e2e4fe5c30e46e2359ff881fbae889f7","datavalue":{"value":{"entity-type":"item","numeric-id":593777,"id":"Q593777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$AEBDDE33-A64D-4744-988D-5F88821F6ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"813e4388017d1b4d968c00e11724647da439ba25","datavalue":{"value":{"entity-type":"item","numeric-id":1686839,"id":"Q1686839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$5F5057E8-EAF1-492B-92C6-E8FE2F76A1CF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$F14EB139-976A-49BC-B0D2-19E57D4073CA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1095658$99328137-E5AD-422B-BE11-140A6D796435","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4e3f6cf2f28f600dff5ef4871b70c0f6b45794f7","datavalue":{"value":"This paper presents a randomized parallel algorithm which finds a maximum matching in an n-vertex m-edge graph in \\(O(\\log^ 2 n)\\) time using \\(O(n^{3.5} m)\\) processors. This result improves upon the \\(RNC^ 2\\) algorithm of \\textit{L. Lovasz} [Fundamentals of computation theory '79, Proc. Conf., Berlin/Wendisch-Rietz 1979, 565-574 (1979; Zbl 0446.68036)] for deciding if a graph has a perfect matching, and the \\(RNC^ 3\\) algorithm of \\textit{R. M. Karp}, \\textit{E. Uppal} and \\textit{A. Wigderson} [Finding a maximum matching is in random NC, Seventeenth Annual Symp. on Theory of Computing (1985)].    Other results presented include \\(RNC^ 2\\) algorithms for vertex-weighted matching and exact matching (a perfect matching which uses exactly k edges from a given edge-subset - a problem for which no deterministic polynomial algorithm is known), and a simpler proof of a theorem first proved by \\textit{L. G. Valiant} and \\textit{V. V. Vazrani} [Theor. Comput. Sci. 47, 85-95 (1986; Zbl 0621.68030)].    These results follow from Tutte's theorem relating the existence of a perfect matching to the invertibility of a certain \\(n\\times n\\) matrix [\\textit{W. T. Tutte}, J. Lond. Math. Soc. 22, 107-111 (1947; Zbl 0029.23301)], Pan's \\(RNC^ 2\\) matrix-inversion algorithm [\\textit{V. Pan}, Lect. Notes Comput. Sci. 206, 504-521 (1985; Zbl 0598.68042)] and the ``isolating lemma'' introduced in the present paper: if S is a set of n elements, each of which is assigned an integer weight at random from [1,2n], and F is a family of subsets of S, then the probability that F has a unique minimum-weight set is at least 0.5.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095658$C9060398-A716-4AF4-A374-3798BB130732","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$0F48255A-B0D8-458F-974A-2F847B315B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$AE8915CB-5119-4C2C-967B-DFA0D718C0DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$635F4C27-164C-40D2-81B2-D6E02C1FCF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$8B544C8E-CDF0-40C6-B8C6-B377B6B2A435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$EA20885F-8765-4DBB-B23E-E8F80B7F8ACC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a14345b0b281fb0c86671bb33b6a3731fde6ff8b","datavalue":{"value":"4028897","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$6CCF517A-8148-444E-ACD4-4900A62862CD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59b0c1a02a224b9fb659082e53fed4a02f3d9545","datavalue":{"value":"matrix inversion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095658$DDF2C145-2F14-4B11-B7F8-97AC22808EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06cae65688d3385aec26afb1fc9e9a3ede5455e6","datavalue":{"value":"probabilistic methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095658$ABE5F46A-4942-448C-9567-F46FA190268A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e90c8bbcb2b3071e9cf12484ec997d7e44a49b26","datavalue":{"value":"randomized parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095658$6EA80AE6-8887-4E9F-B891-C11D00C97B5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3842779000597abe3dc3cef2451250276bc01d5","datavalue":{"value":"maximum matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095658$C2DB9E6E-BB51-450C-BFB6-100CB753FC56","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"82f0ccefee94ee5569da1e5a9346c49d641fb0a2","datavalue":{"value":"Q30053548","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$9A1B9B44-FB56-4DEB-8F0B-7F822916DE28","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$59C6A7C4-65B7-4438-B661-C5CD461BCC87","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$B169167C-EAEA-4E95-B469-5EA82E3244CA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$1B774310-1660-4794-868D-5BF81572C1F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"857d76293368de223128367201210af212393e8b","datavalue":{"value":{"entity-type":"item","numeric-id":4124326,"id":"Q4124326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$BC0D2B77-90E3-4ADB-8346-320E3E28DCA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$E251EB9C-1FFA-47AD-A1F8-830F5E8AB611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2ccaa8b67605d1442f748d22b53e4b3e37cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5564386,"id":"Q5564386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$4DBF3813-005A-432C-AAF4-7D5ED678DBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00c2ebb0451fb64953bc14ef9837478a59b6902b","datavalue":{"value":{"entity-type":"item","numeric-id":1103637,"id":"Q1103637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$15F3FC97-2B52-4290-BE38-1D05100C69A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"310ec4e9bf739fc2741b5a947cedf96624f64247","datavalue":{"value":{"entity-type":"item","numeric-id":3732972,"id":"Q3732972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$F1541470-1045-4CA6-8DC2-ACC6CA053E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4324d74dffdd686a688ce05fefc1066bdbeda16a","datavalue":{"value":{"entity-type":"item","numeric-id":3936213,"id":"Q3936213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$B7950D6D-6557-4608-B2D2-B6D423F542F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf662f3ea9ade9756d7d0b129beeab7ffca49810","datavalue":{"value":{"entity-type":"item","numeric-id":3031945,"id":"Q3031945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$1C66577A-24B0-458A-AB9A-7DBCF9EBE781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45693627939fec63d2836fa11bb5f307d8dbed5a","datavalue":{"value":{"entity-type":"item","numeric-id":3899517,"id":"Q3899517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$AC1D3966-B32A-4B96-B7A1-76D3D7E93382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfba955c32dc153431f5c99ab1d6a49daa930c11","datavalue":{"value":{"entity-type":"item","numeric-id":5785127,"id":"Q5785127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$2F5B57F5-5E1F-4FEA-95E7-FB68A34E1161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$CBFFD17D-AB61-4B24-BE9E-3C4E87AB04AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f48bea928b77412defd29091d29266e33575d210","datavalue":{"value":{"entity-type":"item","numeric-id":3034827,"id":"Q3034827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$59C65981-596B-4D4A-A2D5-90D49038660B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb5037acc3949cbca8f8e77ab83b58c3f57e4b13","datavalue":{"value":{"entity-type":"item","numeric-id":3732965,"id":"Q3732965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095658$E641EDE2-0058-4E9A-9D5E-894FC3AA403B","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"a204c8ded19d1ed431760b212b2e881e0af50b2e","datavalue":{"value":"journals/combinatorica/MulmuleyVV87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095658$A778EBDC-9006-4F3B-9DEB-8A1FEEF5CB01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"789dfeb7dd750449143ccca480f4ecc23c02e5e7","datavalue":{"value":{"entity-type":"item","numeric-id":1103639,"id":"Q1103639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9abb15373ac5da6ae3298abdb23043195e0c59d","datavalue":{"value":{"amount":"+0.9110758304595948","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095658$BD68DABB-F4A2-4B86-9766-ED875127AC9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b4cc1e79cfb1f8999aed5e3509513706dab69b7","datavalue":{"value":{"entity-type":"item","numeric-id":3031945,"id":"Q3031945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b7638c2191c04920b4271a24b9efc22dfb3fdfd","datavalue":{"value":{"amount":"+0.885726273059845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095658$4E97876A-481D-44C5-8B6F-9BCD6D5DE152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91f39a0f9005943790e7f4148d58e586fce7e88a","datavalue":{"value":{"entity-type":"item","numeric-id":1073573,"id":"Q1073573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07ae54a064f47fe6398e1b0a9adc3a6c2266d6d6","datavalue":{"value":{"amount":"+0.869347095489502","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095658$3B0B31BD-B12F-4B31-B618-F2789D6866A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93c28aaf438b3a1d2a0175c17f3015d3de01b647","datavalue":{"value":{"entity-type":"item","numeric-id":1103637,"id":"Q1103637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"129ba7b9e2deee264e9ad4abd440d2e01b291e24","datavalue":{"value":{"amount":"+0.8683396577835083","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095658$63129F4E-1226-4C57-BE79-D16A0487B6CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b2dc7dc67c38d5cf3d4bb60dfacc01308be51a7","datavalue":{"value":{"entity-type":"item","numeric-id":4376193,"id":"Q4376193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df6cd6bc8d84efb33f39919109f9cd527d5f11e5","datavalue":{"value":{"amount":"+0.866851806640625","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095658$12ECD3CE-9AA1-4F93-8322-E45EE90767A1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Matching is as easy as matrix inversion","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Matching_is_as_easy_as_matrix_inversion"}}}}}