{"entities":{"Q759771":{"pageid":761620,"ns":120,"title":"Item:Q759771","lastrevid":64121901,"modified":"2026-04-11T17:47:13Z","type":"item","id":"Q759771","labels":{"en":{"language":"en","value":"A perfect matching algorithm for sparse bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3882482"}},"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":"Q759771$22F01EF7-5F4F-434B-B727-5D00444F736E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b01d6c64eec8d2d6c5ddd4be67e928d26c671bc","datavalue":{"value":{"text":"A perfect matching algorithm for sparse bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q759771$A7F22A1C-7124-42D6-9AA7-7B086F7A46CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7dfc35efbe995aff2faf498357769404e4548467","datavalue":{"value":"0554.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759771$7DD6E713-8E90-40B9-A373-F2BD955B7770","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4dcdf02907aafda9b809f09911bb0cdba98dda9f","datavalue":{"value":"10.1016/0166-218X(84)90026-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759771$24CEA2C8-A093-4828-94B1-AB64BE9F3FAB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17512dfd0c0c1f581a9213c4ae2148baf7c39aee","datavalue":{"value":{"entity-type":"item","numeric-id":759770,"id":"Q759770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759771$D8BD1642-7B59-42B9-8492-B3AA8256961E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759771$1C3AECBC-669D-4138-BF91-C222A3B0A5BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q759771$3D0DCFA9-DD1D-4DCB-AB7A-C8B264328057","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d99132c25ac292e2de657c1e0cdcadb2f27075e5","datavalue":{"value":"The algorithms for finding a perfect matching, if any, in a bipartite undirected graph G usually start with a matching (which may not be maximum) and construct, if it exists, a matching of greater cardinality by determining augmenting paths. This is generally obtained through an associated directed graph \\(\\bar G.\\) The paper shows that those edges of \\(\\bar G\\) which link vertices belonging to different strongly connected components should not be included in augmenting paths. An application to the block triangularization of very large, sparse, nonsingular matrices is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q759771$AE745904-BA39-46B9-921F-2EE5AB3FD22F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759771$35604C97-9F11-4EAC-BB9F-07F11DBA16DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759771$3E0E7A87-BE92-464A-928F-0A65B26403F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22c44b064a17de26330e313bdcc761af2f11592c","datavalue":{"value":"3882482","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759771$182A11AC-8B1B-49BE-B0A7-17AF6BED8F04","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19f748a552f24e88cfd6ef298468872c44adea27","datavalue":{"value":"block triangularization of matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q759771$DC0CA3F8-3EC8-4489-8CC8-595BA5411D2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q759771$B3C3BA84-9298-4E2B-9D16-BA0B83861A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q759771$5637C2BE-357E-4EA0-8ED8-7C68637E99ED","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":"Q759771$D10F06A2-67F6-4B45-849A-31890B0BAF3E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7262f6086a4740c85c04327edf809b00b4562f61","datavalue":{"value":{"entity-type":"item","numeric-id":5632356,"id":"Q5632356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759771$58C35012-73B3-45D3-B370-B39023D351BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759771$C7087381-4AAE-4F18-BCA4-B5D25D7E17A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759771$B3614784-D91A-431C-9A2E-006FED08E8B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c6fbbb8bb483ccccbef2e179903d54cebfa5cb13","datavalue":{"value":"https://doi.org/10.1016/0166-218x(84)90026-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q759771$CAA311D4-B8A7-4839-AE57-F26F0DA8C447","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b59b55c336771dbe3e53a0e3396673d7c2490ebf","datavalue":{"value":"W2078902693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759771$E1925736-5566-4A89-BA93-78D06490B87C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2940a5b4fce82e61f16edbba6931d7e61c0d1aec","datavalue":{"value":{"entity-type":"item","numeric-id":1853135,"id":"Q1853135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e53492620aab8a462eb104b64193c4434dcd497c","datavalue":{"value":{"amount":"+0.841637909412384","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":"Q759771$66DE63BC-AF10-41E2-98EF-380CBC2AE638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0292eb0850ecd744aa687188b36f66830221a3d9","datavalue":{"value":{"entity-type":"item","numeric-id":4370201,"id":"Q4370201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d705044c9aed407fd069abc2a7feaafe530f4d91","datavalue":{"value":{"amount":"+0.8176679611206055","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":"Q759771$6A516D34-7AF5-411D-85A3-D864B771A375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"756eb21d7ac6afaec417269c23d186c28302c16a","datavalue":{"value":{"entity-type":"item","numeric-id":2322505,"id":"Q2322505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9435cb05cabcc9b61c052f86cdda11e82ccd3fd5","datavalue":{"value":{"amount":"+0.8157210350036621","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":"Q759771$0CD7709A-C3D5-499C-A97D-D1D1B96AA32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfdde07b387b1fbbb6b47169e620ca99dd249c87","datavalue":{"value":{"entity-type":"item","numeric-id":4013602,"id":"Q4013602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af9cf9b7268383447cfc295ff87f8eac5ac9bc1f","datavalue":{"value":{"amount":"+0.8151422739028931","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":"Q759771$141FEF45-2B86-4E84-B51D-24E513448355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e7da8fd1e7a8bfff338e64e4e3d5bd17d94edcb","datavalue":{"value":{"entity-type":"item","numeric-id":751274,"id":"Q751274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7de243f1f7876be3d699dae8615497f83af93478","datavalue":{"value":{"amount":"+0.8145374655723572","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":"Q759771$E19933B5-4162-4AA9-8000-592F9ECA8715","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A perfect matching algorithm for sparse bipartite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_perfect_matching_algorithm_for_sparse_bipartite_graphs"}}}}}