{"entities":{"Q1116690":{"pageid":1127439,"ns":120,"title":"Item:Q1116690","lastrevid":69680796,"modified":"2026-04-13T08:40:21Z","type":"item","id":"Q1116690","labels":{"en":{"language":"en","value":"Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090787"}},"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":"Q1116690$165EAC5A-D1AE-4309-8D6B-ED4C78C38211","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"11882ef1422de7c4a525dce58586ecc6ad8a3895","datavalue":{"value":{"text":"Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116690$74711F28-FDF8-4518-B1CC-C507F440A96F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"27bde8868a9beaa86ee70a3c1e26ced4c5479971","datavalue":{"value":"0666.68033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116690$C3910550-5368-4FC6-A0CE-E238F6548C6C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0ae2e08438d02e9e18d3ec0aed27765ff1dd004f","datavalue":{"value":"10.1016/0304-3975(88)90120-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116690$C2933191-9DEA-4005-A0FC-55F499720F84","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d1c5666cfcb8034d94e72905fe0b245c5645906","datavalue":{"value":{"entity-type":"item","numeric-id":233438,"id":"Q233438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$65DA3AA6-3C69-487E-A5E6-7C2C78E97182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"572a13162b6df712d7941005f95a34b361dad87b","datavalue":{"value":{"entity-type":"item","numeric-id":396628,"id":"Q396628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$319A00B2-D061-47F6-B363-6EA62443222F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$5429439E-B540-4714-A24B-87988E9D0396","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1116690$E9508AAA-B3B8-4618-91AE-EA6929DA4F6B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bec288f805ff0dca432cd57ba8b1b549b2762578","datavalue":{"value":"The authors present a parallel algorithm, which constructs for each graph of minimal degree 1/2 n a perfect matching and a Hamiltonian cycle. Sequential constructive proofs of the existence of perfect matchings and Hamiltonian cycles are due to K\u00f6nig and Dirac, respectively.    For lower degree ratios the authors prove, that the perfect matching problem is as hard as the general perfect matching problem. That means, a polylog time polynomial processor algorithm of a minimal degree \\(a\\cdot n\\) for a smaller than 1/2 would imply the existence of such an algorithm for the general perfect matching problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116690$A376CE73-4E73-4F73-8083-6659FE9F65BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116690$C648361D-58BF-40C5-BAED-6E32191DED82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116690$9BBAF323-FD16-4AA3-80DC-0AC720F2859B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116690$2B2DA533-7B29-4DA1-8DA5-34CF2B6E4368","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0966c8129c126c930faf7f6c3aa944f0348142da","datavalue":{"value":"4090787","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116690$A6F0D9F1-6DFD-4B21-B524-232063BAA962","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"430563bb2bce5405485dbdc07f1ffbea12a8c32e","datavalue":{"value":"matching completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116690$DDD8F628-21F6-4E92-BAA5-F249861A8685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116690$0090EA7C-9862-4998-845B-CCA1752A6F31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116690$012FDCB6-C866-4C90-8C7C-A8CD9C466FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116690$7C9B92BE-F576-4904-B3A6-5E7F45050D4D","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":"Q1116690$08B680AF-BA5B-4A5D-A0C8-24F610FAA6BD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3aefaa1fe5faab12728571c48c13e5cfc1d90a2","datavalue":{"value":{"entity-type":"item","numeric-id":1242149,"id":"Q1242149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$625C0769-CF46-406D-90BD-67D37AAA7E0B","rank":"normal"},{"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":"Q1116690$9E9BAC50-189E-4ACB-BEFF-CFC730241E8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$D7E426B1-C1DC-449B-A9A8-239EA37D7BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ced7c3062c508a536ad4b53e4afba4be88eb5cb","datavalue":{"value":{"entity-type":"item","numeric-id":1185245,"id":"Q1185245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$6369A6BF-9BD9-4D8A-BC1C-088114A0C620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d4bd16b8f988e4232f1989a0f22132674569ade","datavalue":{"value":{"entity-type":"item","numeric-id":1079363,"id":"Q1079363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$C418B33B-6755-4E76-90C5-802A699794B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c0428aece4fd742530f4423ccbd5329e7093277","datavalue":{"value":{"entity-type":"item","numeric-id":1108039,"id":"Q1108039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$D567931A-EE64-44AE-8C53-8BE040245682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0262c7ca9d46cfb4cf3512f2a0333529706ee62","datavalue":{"value":{"entity-type":"item","numeric-id":3684121,"id":"Q3684121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$0D0E69DB-AB93-4D00-B8F2-50F3D1B5225F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$2723BCC6-B7C1-46AA-A087-D3ADD9C120DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07adfa7411d8716c42e7a81a35a8dc21f533009d","datavalue":{"value":{"entity-type":"item","numeric-id":3951543,"id":"Q3951543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$44E26190-BF50-46BA-A4FA-7C064D3F6B57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"720cb0112745e0fc4d414a8652264da0bad7fa31","datavalue":{"value":{"entity-type":"item","numeric-id":3731028,"id":"Q3731028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$A495A8D5-4260-40EF-991F-124E4985A5A8","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":"Q1116690$472BC45E-1BC2-4EE7-8B93-80510C6036BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2d7941d0b26099a80a70765368bbd5212826ec8","datavalue":{"value":{"entity-type":"item","numeric-id":3677509,"id":"Q3677509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$707981A2-D88D-4E44-87BF-999FB35C24F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05f132c6521c12283446aaf341248df05dd5b786","datavalue":{"value":{"entity-type":"item","numeric-id":3904540,"id":"Q3904540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$339F343E-52BB-4371-9870-B12181FC745C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$DB67BCFE-218A-49E7-A83D-9B391B39C194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec62482a6f1abfd15d9d0aa6d0ca02f4b7a14835","datavalue":{"value":{"entity-type":"item","numeric-id":1095658,"id":"Q1095658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$86A8D941-B919-48D9-AB45-ADD60D4CCD6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$8FDD8011-03E6-46CB-BC16-E4BA1AC3030B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd64611a01b2447ad8faeff4c7e0fda50839aa4b","datavalue":{"value":{"entity-type":"item","numeric-id":1262782,"id":"Q1262782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$A7D0B216-F1A9-4712-8CF3-45FE5D8F2554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$715A03A5-ADFB-424D-8426-8D03469F43AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dac16590ead14d6d4e12e819799d8a5842538ef","datavalue":{"value":{"entity-type":"item","numeric-id":3786504,"id":"Q3786504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$D877A71A-53F6-4200-8B43-4C32245680EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9db4a207e2ab9eef002ed1bcd0688887d186bc","datavalue":{"value":{"entity-type":"item","numeric-id":3957960,"id":"Q3957960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116690$AE9965D2-6613-4E13-8379-80DD17B31A32","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e341a737ddde980672952001e4b1c9060bd90581","datavalue":{"value":{"entity-type":"item","numeric-id":4275334,"id":"Q4275334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61e40231ab491f27eb96ee42d3652e6889869670","datavalue":{"value":{"amount":"+0.8939312100410461","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":"Q1116690$A8017025-FF29-42CA-B45E-5CAC1458F20F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ceff47858bf06fc5f9a01de6d31a1e4c75a2e73","datavalue":{"value":{"entity-type":"item","numeric-id":1341686,"id":"Q1341686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69c6a3ce96d3a781f9d0d0bd5ab863795e0e8898","datavalue":{"value":{"amount":"+0.8932308554649353","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":"Q1116690$D8AD50DE-267B-4CD8-A6BA-5566F7A8B876","rank":"normal"},{"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":"12bb46f52444dbdc05c9cd1ad6447ddfd7eb14a5","datavalue":{"value":{"amount":"+0.8182177543640137","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":"Q1116690$1BD95F02-0274-4E50-82F5-BDB88605FD1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3942921f36a9a3455cc2d6ccb0fc3b5648bedac4","datavalue":{"value":{"entity-type":"item","numeric-id":2741350,"id":"Q2741350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"610ec84dd11a0ef2e56aefd27a9ea39e2b183e7d","datavalue":{"value":{"amount":"+0.8063282370567322","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":"Q1116690$E4F201B9-AF6A-4757-A174-FEEB6C8E3AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08b69a43dcd1d6b96ea96c5a829f7c99a640a719","datavalue":{"value":{"entity-type":"item","numeric-id":2365177,"id":"Q2365177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdcf2763f69be9cced0d2050e9ccf114c00167dd","datavalue":{"value":{"amount":"+0.8051678538322449","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":"Q1116690$94762B04-7DA5-4171-B7BD-FF982E989774","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel_construction_of_perfect_matchings_and_Hamiltonian_cycles_on_dense_graphs"}}}}}