{"entities":{"Q1743490":{"pageid":1754232,"ns":120,"title":"Item:Q1743490","lastrevid":72406383,"modified":"2026-04-14T04:41:39Z","type":"item","id":"Q1743490","labels":{"en":{"language":"en","value":"The matching extension problem in general graphs is co-NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6859592"}},"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":"Q1743490$520D66FF-A60A-4EBC-B898-8BC688A579C5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e2547a1b00258fa38a991b0bd508ca015dc7d869","datavalue":{"value":{"text":"The matching extension problem in general graphs is co-NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1743490$444D29BD-312F-4C00-BC00-AEE09AF95DE8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd53ae4dc89ad1e5461e7408ce2a60bf2ecd1d99","datavalue":{"value":"1387.05203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743490$9B337B04-883C-493B-88DB-6FFA12B75630","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fa1a81af5008d185caa490b84b7047f7e328800","datavalue":{"value":{"entity-type":"item","numeric-id":1743489,"id":"Q1743489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743490$76263D81-5E21-4A32-9E97-5B326BCD3C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"420534450a0950e0ee370ffceb1104acf4e79ec1","datavalue":{"value":{"entity-type":"item","numeric-id":325444,"id":"Q325444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743490$0DE06CA4-4F6D-4205-A4D6-A32E56DA9A3A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743490$28342345-23BC-4191-8272-53C01E5BAF8A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"30b43d2fa1cf1a5be87fe107e165135cb84cc159","datavalue":{"value":{"time":"+2018-04-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1743490$A8DA1FD8-0C08-434C-BA7F-8967E373D261","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743490$751D515B-36CA-425A-846E-BE0A9DA00035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743490$87B619F9-6E01-43C1-86D9-6E6E26AC6FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743490$B159A34B-23EC-4884-8EC6-F2266CEF1F1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9f45c84aa70f5d3ef5839ce3877ee8820f13ffe5","datavalue":{"value":"6859592","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743490$BC8DE4CE-5A58-4DB3-90E2-A8714EC97524","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743490$C5A66F17-3EAE-4A0E-8FD3-B743DBDAF830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743490$D423C877-21FD-4185-A56E-51380E2BE68D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa0a30968dc4986c7e21f80ec13ef1aa4fd3291d","datavalue":{"value":"extendability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743490$239F9EB1-C8E2-4C1F-B70C-B45C5D0B0BDE","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":"Q1743490$B9AF73FA-5E7B-4BD5-B176-79FF3EE71ED7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9f93c39e4ae63836318c8ac3bc082a46ef2b83c6","datavalue":{"value":"https://doi.org/10.1007/s10878-017-0226-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1743490$01E1D14A-F6F2-4ACB-84A2-7924902E3F8A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"affc5b974be1d407d6f94c946dcf09461ce78106","datavalue":{"value":"W2775963553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743490$0E552320-5D6C-42E9-8027-91FB5BA202A8","rank":"normal"}],"P223":[{"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":"Q1743490$E0B30033-CCC6-4928-BBBE-74DF57888A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743490$4AC2988A-9F10-4602-9309-C395E390FA5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81050da671432241c156091286b41dd0c5b00e7a","datavalue":{"value":{"entity-type":"item","numeric-id":293170,"id":"Q293170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743490$78F7ECE6-DCDE-4571-8181-EE1DD7031931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d65558089a090b2f0fdd69c10c0a9d1b40728a97","datavalue":{"value":{"entity-type":"item","numeric-id":1322235,"id":"Q1322235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743490$97FC6333-497D-41D1-B8E4-50D96E22631D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"850ea206c46b8f21630484767b8d153e7411248f","datavalue":{"value":{"entity-type":"item","numeric-id":3601930,"id":"Q3601930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743490$49012342-B500-43F4-9777-4814DD8CC4A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f2d59fb842b1cbb3074e36f01128ed37128a7d4","datavalue":{"value":{"entity-type":"item","numeric-id":2497479,"id":"Q2497479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743490$656404FC-C101-448D-942B-2C6E2ABBB447","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a432c9770aecb20ac09530f8fe3490ce30bfd3a","datavalue":{"value":"10.1007/S10878-017-0226-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743490$785F5590-EFFD-4E16-A662-00509ECA85AE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21ab46024e142f01242289c6f8bb21690363d24e","datavalue":{"value":{"entity-type":"item","numeric-id":5937599,"id":"Q5937599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c496a270a718d46c6f921bb4bea898b19aa3281e","datavalue":{"value":{"amount":"+0.89624697","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$1649B2F9-A2AD-42BB-BD94-4A3C868C9AA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46d8e1958ba8ce16f6e11e8b57338a32c303ce65","datavalue":{"value":{"entity-type":"item","numeric-id":1322235,"id":"Q1322235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44fd54825eb057a3714605085da82dc676ab30a5","datavalue":{"value":{"amount":"+0.88426274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$276B7DE1-1E60-4139-9BB6-2ED77445ABED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9355c97110d220cd9fcd9128273bbc3e51bcc1a1","datavalue":{"value":{"entity-type":"item","numeric-id":4393233,"id":"Q4393233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b3abc682dd3d8a77f735085e0fc2d77cedc3bcb","datavalue":{"value":{"amount":"+0.8816984","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$639AB036-EFF0-4807-85CF-032528DC33EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"211173805547e4cc7289ee7e59dd8baafc073d88","datavalue":{"value":{"entity-type":"item","numeric-id":2370426,"id":"Q2370426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1502fcc42a37ce67f07a052aac159cae14d9ec14","datavalue":{"value":{"amount":"+0.88020337","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$8BAA06CD-9B32-49CF-8823-F5B8842E03E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08612b36a08aa2dc6d3b86517dbec3aa1ec9bce9","datavalue":{"value":{"entity-type":"item","numeric-id":4528770,"id":"Q4528770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68802589e21f7c3229562fdd1eb74f3a6be64145","datavalue":{"value":{"amount":"+0.87522304","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$3AFB6993-DF27-45D3-9892-E7711E2578AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3ae7b50c7608d2c7c8e94b507a75ffa7bae5321","datavalue":{"value":{"entity-type":"item","numeric-id":650325,"id":"Q650325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d466e73d83d055feab1612d0d705122df371cafa","datavalue":{"value":{"amount":"+0.8747927","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$F0A70AB5-D573-4A35-B23F-A4F11D875496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5fa981bf417274d5f27f666b4b147c681958896","datavalue":{"value":{"entity-type":"item","numeric-id":534332,"id":"Q534332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"439d5bed8136154d8c861d1224adac46a6782bdb","datavalue":{"value":{"amount":"+0.8729646","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$18125A9D-DE89-424A-A758-30FCE728A69C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dff881a8f2911b96b065fc1cf38468f703ce4b75","datavalue":{"value":{"entity-type":"item","numeric-id":1584277,"id":"Q1584277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04fa10a74c46721d510c0216d2ffa8719fd6e90b","datavalue":{"value":{"amount":"+0.8726301","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$DD271E80-BBD1-447C-8B4A-FA700C7BE264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d73ce4ab42eb3b33e7d92413ac253176dab3d9c0","datavalue":{"value":{"entity-type":"item","numeric-id":4873744,"id":"Q4873744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53657b3c53980cc7fa1ae59c136b6d4a63caafaa","datavalue":{"value":{"amount":"+0.8725574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$AB3E8AAA-841E-430C-9130-9D261B86A687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dfa139cff25940aaee87cfa90661aefaa7155f3","datavalue":{"value":{"entity-type":"item","numeric-id":5202207,"id":"Q5202207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6592a8a030f7e08acb0a40c878838db42dab2857","datavalue":{"value":{"amount":"+0.87055624","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1743490$0B9836D6-DE29-4ED4-9391-ED7850D3F0BC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The matching extension problem in general graphs is co-NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_matching_extension_problem_in_general_graphs_is_co-NP-complete"}}}}}