{"entities":{"Q2643795":{"pageid":2654538,"ns":120,"title":"Item:Q2643795","lastrevid":50152388,"modified":"2026-01-13T07:00:03Z","type":"item","id":"Q2643795","labels":{"en":{"language":"en","value":"A list heuristic for vertex cover"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5183109"}},"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":"Q2643795$E110050F-9F7F-42D8-909C-7A8B1D3F008E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3c4a80777dae9b119206de0b743c3ce3f91f0bcb","datavalue":{"value":{"text":"A list heuristic for vertex cover","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2643795$918DA8A4-BE4D-42B3-B18C-FC836A87567E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c9cdac63cfa8a4b3830e36be3fa4131207f4ff4","datavalue":{"value":"1125.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$642C53C1-3EBB-4060-AF5E-5AA5F9667C20","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"65972bc972e8e61e898817b9b35e697b52926a0e","datavalue":{"value":{"entity-type":"item","numeric-id":2643794,"id":"Q2643794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643795$FA5A25A7-9B87-4E54-8A3D-C7C73DF54493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8f80dfc7d569f12c09d99bcc3b3496b227a33b7d","datavalue":{"value":{"entity-type":"item","numeric-id":173840,"id":"Q173840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643795$BDBE5532-3C7F-41AB-ADBE-61EF7B1A0600","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643795$6859EBB6-5108-423C-BB70-0C00D3BF3239","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d1b09aca3aa7cf2e4777f30c65432cb22c512993","datavalue":{"value":{"time":"+2007-08-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2643795$1EF2471C-585A-4875-949B-270936BF7B34","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"160e3fea8a4065870a5cb1341340a78935484121","datavalue":{"value":"A class of approximation algorithms for the minimum vertex cover problem for graphs is studied. These algorithms, called list heuristics, handle the vertices in a given static order based on the degree sequence. The authors prove an approximation ratio of at most \\(\\sqrt{\\Delta}/2+\\frac{3}{2}\\) for a nonincreasing degree sequence, and show that no ordering can guarantee an approximation ratio of less than \\(\\sqrt{\\Delta}/2\\), where \\(\\Delta\\) is the maximum degree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643795$4E5C7452-3C48-476E-BC9E-697825361B81","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"28b1fb367b3a6335e647ddbd540f63d134723dd1","datavalue":{"value":{"entity-type":"item","numeric-id":222481,"id":"Q222481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643795$3EFBC012-DEDA-4A37-9533-5A9B3DB68677","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$95F833AC-BAC9-4D56-8F67-D44E0270B046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$745123B1-58EE-4E6F-8261-CFB32EADAFEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$4C13CB1C-F2E7-43E5-848F-A173D62BF078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$CC09CB5A-E5DD-4F5F-8FC4-47450D69FCD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$F40256DA-450E-4300-B3A6-5F822BB14BA2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e05d1e8255f2cebc2410a71a2ee020348e87f8f","datavalue":{"value":"5183109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$598B4C46-5626-4038-9E09-11F1033AC544","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643795$7AD6F3EB-0560-42F1-9B46-9D37B8008B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643795$9C9947C9-91F5-4B4F-A6FB-5D03ED134702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a833dd6223ae422a02351baabb497d2945ba3c7","datavalue":{"value":"list heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643795$385B5A95-7334-49A8-BC02-11CE954B51ED","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":"Q2643795$5857F47C-DEC5-416F-8B81-CB7C99F4F915","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"46435097a9ba576321c730a160c3eb371f9e24aa","datavalue":{"value":"https://doi.org/10.1016/j.orl.2006.03.014","type":"string"},"datatype":"url"},"type":"statement","id":"Q2643795$67C1AD23-4A0E-436D-9298-FFB77015BD5A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"439b9212883fca248cf09ea66274293c949115d7","datavalue":{"value":"W2095553101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$CD1994DA-28C6-4D6D-B6CB-6931DC97429B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643795$F45062C1-3426-466D-9720-C086D4F06B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a20d09513baf32113955ba3ecf79c8e2d6ab34f2","datavalue":{"value":{"entity-type":"item","numeric-id":3512428,"id":"Q3512428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643795$9D438C4B-9708-4F54-AA55-846AB07FEF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643795$AC650C39-0375-4DC0-B3EC-72C841A4A197","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f2f9b76ee29f30640b482b76bf96227811541983","datavalue":{"value":"10.1016/J.ORL.2006.03.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643795$C02D11C9-EEA2-46C5-8138-2775BFD3A124","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3310fad5c21fa629c022001adfa107528ad75d4d","datavalue":{"value":{"entity-type":"item","numeric-id":1779691,"id":"Q1779691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fc009845e0b7951be20bc1f8f6662e730053a62","datavalue":{"value":{"amount":"+0.8268254399299622","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":"Q2643795$D6DB7A34-65F2-41DB-9639-067D896785A4","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":"0b6998e74d4d004e11896bf260bd6245d70aee99","datavalue":{"value":{"amount":"+0.8260507583618164","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":"Q2643795$9686013E-D173-4EFC-B5F4-21A76876969D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62dbe2c2f14150e9bb5b1027c72dd8c5e5b94d80","datavalue":{"value":{"entity-type":"item","numeric-id":5406226,"id":"Q5406226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e83da4c4c5b7676c6b80f28f143743840196b800","datavalue":{"value":{"amount":"+0.8226096630096436","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":"Q2643795$5DBB8D60-042F-4847-B9AC-4C3B1327F3FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fba08533f3426db179a33f027889c5c044c176a1","datavalue":{"value":{"entity-type":"item","numeric-id":2870054,"id":"Q2870054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc1f560a1b2df5131801bb2a1175ec024acc8f13","datavalue":{"value":{"amount":"+0.8204885125160217","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":"Q2643795$8CC2752A-25C6-4AAA-9327-ADCAA24DBF54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc71658269fdab0ad408f1578495c31c16e237d4","datavalue":{"value":{"entity-type":"item","numeric-id":3583300,"id":"Q3583300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d45f4d139c01f3c8b82fffe665d1be587623a846","datavalue":{"value":{"amount":"+0.8172320127487183","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":"Q2643795$258B63EF-6F20-434F-AE56-9B38F05D5F47","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2643795","badges":[]}}}}}