{"entities":{"Q1123907":{"pageid":1134656,"ns":120,"title":"Item:Q1123907","lastrevid":49298824,"modified":"2026-01-06T22:28:40Z","type":"item","id":"Q1123907","labels":{"en":{"language":"en","value":"A decomposition strategy for the vertex cover problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110742"}},"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":"Q1123907$8E26FBC9-B726-4A52-BBEF-5AA9A6265DF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d0266fb192b26987c5926ff3da7e1c988066258b","datavalue":{"value":{"text":"A decomposition strategy for the vertex cover problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123907$A6031CD6-D129-43C5-91B0-D454CB79D885","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b8e0c6603b2a3292c5ec94fbc2bf88e3a6bfe708","datavalue":{"value":"0678.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123907$51D33C20-E0B3-4A0A-8339-D9FC86023D78","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"db28ea17b9c3fa6f7e6d8286e9a1182047ec5bd4","datavalue":{"value":"10.1016/0020-0190(89)90091-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123907$C7902F3D-26A2-4154-BBD8-33E809788E48","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd94e4e7f27f948a7315c2ac01ba439ef6354378","datavalue":{"value":{"entity-type":"item","numeric-id":235657,"id":"Q235657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$78B03C4B-E5F1-4052-B632-67C38D93BD33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3de34c40bbd436145163ee502934245d6246cef6","datavalue":{"value":{"entity-type":"item","numeric-id":173870,"id":"Q173870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$A9ACE509-5B8B-41E5-B2FC-00B6E27DB6C4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$7578C3A4-1B51-40EC-96CB-DC4AF14D9996","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1123907$2938D20E-B266-44FB-8253-52E5E171FD5A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"58156253af772a5f86d8607249b56a838af2fe28","datavalue":{"value":"The authors introduce a strategy to decompose the minimum weight vertex cover problem on a graph \\(G^ n\\) into smaller subproblems. They use general results relative to clutters.    The minimum vertex cover can be found by solving of a sequence of subproblems \\(P_ j\\) \\((j=n,...,1)\\). The vertex-cover problem is solved by solving n minimum weight vertex cover problems for minors.    From the considerations the authors define a family of graphs for which the vertex cover problem is solvable in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123907$B49C8BF9-EF69-4FBF-AA3E-4D833A4595B6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bee1f7445f48f88ea32c13733d6b7ad82b5d2674","datavalue":{"value":{"entity-type":"item","numeric-id":803176,"id":"Q803176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$42BABDAA-5B69-4569-A734-4DB2B1952517","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123907$B33AF4D9-6905-4E01-AC97-90E74D8A0EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123907$98996834-096D-4187-85E1-A2AD3204F052","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9c6f9accbef0ba70d0f13ce0e261a7491fab9e55","datavalue":{"value":"4110742","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123907$4C811DE7-229D-4C89-9186-8EB9C3E555AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13b7003a29f624e5ce1f28924909187b15f63821","datavalue":{"value":"clutter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123907$A8E4795B-BC95-4EA0-848D-341C84046BF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dd0d7043066fc18c97c64cc2373bc266c0fadc1","datavalue":{"value":"stable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123907$4DE937C2-E8E5-48CE-874A-795606987BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6d9ec77b0669b77734b6831d672122e99e5245c","datavalue":{"value":"minor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123907$956EB03E-E249-45DF-BBB4-C3BE36781A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123907$9B07A085-20BB-4168-8DA3-4C4077A92D80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6ff3e50234a0281f11cc46dea6e57a657fde543","datavalue":{"value":"minimum weight vertex cover problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123907$472F2C62-78D8-4C39-A880-22C085A221E5","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":"Q1123907$667EC221-3D68-41D7-AD97-68D801D7111E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"30453f4d6e67f28337e68f706693cdb81e3ca03d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90091-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123907$EDD02C9F-987C-4FB0-AF4C-255E278B7CB2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0537a9c58d4a75823cddeac638f26e9536f6830b","datavalue":{"value":"W2072913850","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123907$43510FA3-81A9-4C44-866C-C2EB000AA04C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b717ce5476163967b0df9674233704df8f3864c4","datavalue":{"value":{"entity-type":"item","numeric-id":3344216,"id":"Q3344216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$1176E7A8-05EE-439C-8B00-20BA9E002B14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ff5815c38d237a74f6b5a82910f7cd714253562","datavalue":{"value":{"entity-type":"item","numeric-id":3834089,"id":"Q3834089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$46FC33AE-75B3-48E0-AFF5-E7106BAA52DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6ba8beca23cdaad0ac4c8fdb9394466e17ade7f","datavalue":{"value":{"entity-type":"item","numeric-id":1051004,"id":"Q1051004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$AD2D3A42-8F88-4B14-81BC-8016752D6A74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c406cccfaf0baf112bd503da4f4373902a51376","datavalue":{"value":{"entity-type":"item","numeric-id":4093489,"id":"Q4093489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$D72F2813-BA73-45CD-8904-8CB23A64D2DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f79c945ab8de49a03e4c94f42030e55878a2df1","datavalue":{"value":{"entity-type":"item","numeric-id":3270978,"id":"Q3270978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$D92E1648-0F7F-4588-94CA-2A926C6934F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$574331EC-9D8E-4006-A4A7-5AD355C244A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"119d14273a5178c9fdb0109f5da7d88db66c689c","datavalue":{"value":{"entity-type":"item","numeric-id":1245970,"id":"Q1245970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123907$19990765-6FFC-4264-8718-ED742936B4E8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ef715061fb9af0b567f00940891b8fff8af4a0e","datavalue":{"value":{"entity-type":"item","numeric-id":1328583,"id":"Q1328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a923af8fadc12de7642ef75831d776b73c2f2a16","datavalue":{"value":{"amount":"+0.7894109487533569","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":"Q1123907$E6BBC6BD-A35B-4277-B186-CCA0218ED0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7f12c3b1371159e4710169adb27893f24e65a45","datavalue":{"value":{"entity-type":"item","numeric-id":3322143,"id":"Q3322143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21d51f33c3801a9c29b54b5bdffb12153ea43fdd","datavalue":{"value":{"amount":"+0.7882309556007385","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":"Q1123907$80F20E35-9C7F-4215-BA3A-F25346FF5DE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd3e6113f773101d666253c8468ba81b31ae8b85","datavalue":{"value":{"entity-type":"item","numeric-id":4532541,"id":"Q4532541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0597d08fbe3fd24f2f69a04d51ebb51c27c87bd","datavalue":{"value":{"amount":"+0.7847140431404114","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":"Q1123907$C651B00A-810F-44C0-A348-71409DC9DA7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"083c1f348f942fd8acb75b7a35f580a8020d57f6","datavalue":{"value":{"entity-type":"item","numeric-id":2473030,"id":"Q2473030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a91e532eb0a38000f580bd2b6327361f6f1f5e58","datavalue":{"value":{"amount":"+0.7724452614784241","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":"Q1123907$EB4BBA9E-7843-45E5-A094-19052E91CB61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c205189f38bcd79da1552167a2b60128a588e999","datavalue":{"value":{"entity-type":"item","numeric-id":293433,"id":"Q293433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42baa88d619e38b149685cab372e11afc0edadbd","datavalue":{"value":{"amount":"+0.7712018489837646","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":"Q1123907$EECA845B-AE78-466B-8686-AA309A78CC06","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1123907","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1123907"}}}}}