{"entities":{"Q2768405":{"pageid":2779144,"ns":120,"title":"Item:Q2768405","lastrevid":79227161,"modified":"2026-05-06T13:26:12Z","type":"item","id":"Q2768405","labels":{"en":{"language":"en","value":"Linear reductions of maximum matching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1699323"}},"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":"Q2768405$261618B7-275F-48F3-9744-3DB80510BB6D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a704ceefb763b9679e68d7cdfc3aeb33971b22a7","datavalue":{"value":"0983.05066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768405$0072E64E-643F-4464-B891-0AF1E455BF16","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2c5af00fd1fc149dba1e61ff5498f18aaaa6efa9","datavalue":{"value":{"time":"+2002-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2768405$EED3C258-FD6E-42E5-8596-BA8B60DFDC54","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768405$61FCAEE1-7DB5-4690-A822-F12D7A58396C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768405$89B023C8-842C-4A09-BA7D-4BD41494844F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"94f27b194f59e89d3bc98a10861df7599246666b","datavalue":{"value":"1699323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2768405$21CE6CD8-1F82-4AEC-9F53-3615C6668B10","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3842779000597abe3dc3cef2451250276bc01d5","datavalue":{"value":"maximum matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768405$62E3CA9B-A74F-4BDA-BDE4-8EA2BC8BBAFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2048756a75c8d4059ef4461062ea4db6f752f1f3","datavalue":{"value":"biconnected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768405$79820181-6E39-4266-A1B4-B2F0F239579C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"969297229714919f9a950c0dadf0f811afe322e9","datavalue":{"value":"3-regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768405$132A58E0-9A0D-41B1-8085-5418D82B5C22","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8be65cd66158c7fd5243610acab29184eef6acf8","datavalue":{"value":{"entity-type":"item","numeric-id":293200,"id":"Q293200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768405$CF49046C-3B92-403F-817C-34700DF4DBAC","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":"Q2768405$5F9A789A-B123-4CAF-80B7-E2D206C99D74","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"802336dddfa04be1e692bdc8b3375206318d9fcb","datavalue":{"value":{"text":"Linear reductions of maximum matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2768405$F86C408D-0137-4A24-A5BC-9B6539C3AF4C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f97c755ca9b6c82806f4b67202508b6d168d92db","datavalue":{"value":"In 1999, \\textit{T. C. Biedl, P. Bose, E. D. Demaine}, and \\textit{A. Lubiw} [Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms. Baltimore, MD, USA, January 17-19, 1999. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics, 130-139 (1999; Zbl 0938.68063)] showed how to find a perfect matching in a 3-regular biconnected graph of order \\(n\\) in \\(O({\\log}^4 n)\\) time. In this note, which contains no proofs, the author discusses the question whether this algorithm can be extended to similar types of graphs, such as 3-regular graphs that are not biconnected.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2768405$4328DB7B-5DEE-4864-A9F0-D70357C859FD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a65d3702174a536f0cf916db67d42643a023895","datavalue":{"value":{"entity-type":"item","numeric-id":186197,"id":"Q186197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2768405$738C09E7-164D-461C-8911-8C8205B01388","rank":"normal"}],"P1643":[{"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":"89dbd6b9ac2d75d1218b4ffdc0c2537eb893501f","datavalue":{"value":{"amount":"+0.8357294201850891","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":"Q2768405$6384D327-0122-4CC2-8B4B-160CC92710AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e65e54ceffe500e00ba4d80ab495005fc15001a","datavalue":{"value":{"entity-type":"item","numeric-id":1949755,"id":"Q1949755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dc8431fee46ea4851872ca8718d9bd5d27f9894","datavalue":{"value":{"amount":"+0.8318729996681213","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":"Q2768405$478222B5-6AEF-459C-BA8D-77BAF717D3CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"801d506531b533c4280c759a031256e0179de003","datavalue":{"value":{"entity-type":"item","numeric-id":3401102,"id":"Q3401102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f94a0269daeb5b3354a13527fe3d671175e1ee91","datavalue":{"value":{"amount":"+0.8131773471832275","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":"Q2768405$C0044949-E101-4ADD-8EB3-7B0E2462C72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b7fce2fde2babfda3200113ec7b006e4804ed66","datavalue":{"value":{"entity-type":"item","numeric-id":3188982,"id":"Q3188982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25c98468464467327a820328946ce06432775de7","datavalue":{"value":{"amount":"+0.7997737526893616","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":"Q2768405$8C0A71AE-DDCE-42E1-9E92-0A5B8ED2BFC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee69a90fd842670f6dc67cc7f88550858411c34a","datavalue":{"value":{"entity-type":"item","numeric-id":4252281,"id":"Q4252281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e922e02124a43954699518c6e477d8e7e1d0738","datavalue":{"value":{"amount":"+0.7996081113815308","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":"Q2768405$B16BF135-6094-4CE9-8BE2-3A906EC4739F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear reductions of maximum matching","badges":[]}}}}}