{"entities":{"Q3002828":{"pageid":3013552,"ns":120,"title":"Item:Q3002828","lastrevid":57519822,"modified":"2026-03-31T06:17:34Z","type":"item","id":"Q3002828","labels":{"en":{"language":"en","value":"Inapproximability of vertex cover and independent set in bounded degree graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5899301"}},"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":"Q3002828$9154A154-6E84-4491-BEE4-55F6E5C14013","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c1f8cb996b6d9ac4074e0640fe3fd16c4d43219","datavalue":{"value":"1243.68183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002828$C9B7F003-37D5-4478-87E1-C582C00FE69B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dbd0b695fb6fcafddaf81878c9443c3ab8191ffa","datavalue":{"value":{"entity-type":"item","numeric-id":626618,"id":"Q626618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002828$931E0A1D-E8B8-46F3-826E-80FCF840D7B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc0f476358ab3d9fa7f8c58db4d920df08a5d274","datavalue":{"value":{"entity-type":"item","numeric-id":430831,"id":"Q430831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002828$AC41F8D9-F79E-4F29-93AF-620925FAFA43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d14ec0d2c25271c51dc324d4a7cd01ba1a383ba","datavalue":{"value":{"entity-type":"item","numeric-id":178481,"id":"Q178481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002828$96B6F77A-FCBC-476E-A5E0-4346DCAA15CE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"11632bef515b8b0af0e8d65098d262d28b5f8c42","datavalue":{"value":{"entity-type":"item","numeric-id":2816408,"id":"Q2816408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002828$C60C7807-40CA-4D0B-9D43-D8A03ED90D61","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"06770005a3ff7536cedbafe2a793f3c0760af601","datavalue":{"value":{"time":"+2011-05-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3002828$7602C5BA-28C0-4606-AAF0-7164AAE0D7BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002828$BBBBA5B7-D896-44C0-BA6E-C632F5A45C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002828$4A6F7D86-2833-421B-A2E1-4C60423DC387","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6c86739f37b5783a012bb5125d41db36dfaf8e8b","datavalue":{"value":"5899301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002828$F90C9349-6B9C-4063-88F2-717E08D7BFBF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002828$67A017D3-A09F-49B3-9F53-2C3D326C8403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002828$16E3709F-B1A1-473B-A10B-6C231A42D8E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ad842ad959da83378064b3e3e21d1fa80e76ac0","datavalue":{"value":"bounded degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002828$E035B283-A64C-41F0-8AB7-820DA2F03743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4881dceebcfc2cfaaf48b0eeca275f318bc3a7ae","datavalue":{"value":"hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002828$7B37B195-FE9F-467D-BE67-BB46693F37C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002828$E40C8965-1CE4-4B8F-B823-EE552395396B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e088df1fc83158b6e99a19b8d624735c4cb0c49e","datavalue":{"value":"unique games conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002828$0FA7F1D2-53B5-4E98-9BAB-4C54EE4F57CF","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":"Q3002828$B5103532-572B-4DC7-852D-4DDEB7322D85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e495fe865bf8f62409f7346d83fb74f692f40f99","datavalue":{"value":"https://doi.org/10.4086/toc.2011.v007a003","type":"string"},"datatype":"url"},"type":"statement","id":"Q3002828$C71C22C8-6CAC-4F58-B59A-0E533108AC46","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ef7aedc4144d9058584096151e2ce7d416c86826","datavalue":{"value":"W1491127810","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002828$43736E13-3074-45A2-8DEF-3589804AA84F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4e2628acd303d84c254b4987131f39eb0ea900a8","datavalue":{"value":"10.4086/TOC.2011.V007A003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002828$9F54B5AF-2E99-4556-8EE6-54A4E714ACFF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73ee41b10cd5c3acd0ef980639d23857a9c9f1b5","datavalue":{"value":{"entity-type":"item","numeric-id":2475406,"id":"Q2475406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64371c4c51d54a6600126e3af14c13080e3e21ed","datavalue":{"value":{"amount":"+0.8375956416130066","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":"Q3002828$E769510B-8355-4C02-8027-D6A055CDA310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a984c191946cdb38ed399f029c3c2dd521aefe0","datavalue":{"value":{"entity-type":"item","numeric-id":5900783,"id":"Q5900783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7330247b21e9749ed6cc718515ae07dbdc292c60","datavalue":{"value":{"amount":"+0.8308917284011841","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":"Q3002828$5D9F1990-874C-4703-A7A8-42D927758082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"825b87fba54f68d17a58a15d20c962202d6923ab","datavalue":{"value":{"entity-type":"item","numeric-id":5219712,"id":"Q5219712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76cafe3603038acd9ff8ffdceb893aea7368173f","datavalue":{"value":{"amount":"+0.829399049282074","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":"Q3002828$0459C4E1-933C-438B-8452-0EC9F4D7B552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"141060f2e3ed11e3c1570c65949c62a7a7409123","datavalue":{"value":{"entity-type":"item","numeric-id":1281930,"id":"Q1281930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0f851d3cf00b931413e4f6d61101fcf5f78011f","datavalue":{"value":{"amount":"+0.8285666108131409","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":"Q3002828$F671A4AC-EA81-459C-9E8B-31BCF3D64466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ac357fe6b363a31bbac12e45a2bd98be5302c1f","datavalue":{"value":{"entity-type":"item","numeric-id":4737227,"id":"Q4737227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61cf6ead2f70fbfea97a99db08f0278c5c105508","datavalue":{"value":{"amount":"+0.8238677382469177","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":"Q3002828$F8D5F783-0519-4112-BB5E-C4B75523BEB5","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002828$39D2B2CA-FB7B-4DE7-9E38-BBF11082A57C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3002828","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3002828"}}}}}