{"entities":{"Q4376161":{"pageid":6405760,"ns":120,"title":"Item:Q4376161","lastrevid":40898160,"modified":"2025-04-13T22:03:19Z","type":"item","id":"Q4376161","labels":{"en":{"language":"en","value":"Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1116350"}},"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":"Q4376161$BE780228-67DE-4190-8AA0-82A6315354C6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d34b078e91a93b59ee61c564e538c57057d885c","datavalue":{"value":{"text":"Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4376161$0215F634-F4A2-4B24-8D24-34E0E2ED0885","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"305627cca39f405932c00dc995c2c948eb97196c","datavalue":{"value":"0884.05071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4376161$9A827526-F499-4EAD-B34E-268187375C95","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dfb2f9a26fa265bf6a54d4189d4f137a730cce70","datavalue":{"value":"10.1137/S0097539792229507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4376161$C222FD16-9E24-4447-BD45-6C85118BF965","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6528a033086d689548cd6b323306dad1d6651466","datavalue":{"value":{"entity-type":"item","numeric-id":286767,"id":"Q286767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4376161$B1B1B5AC-E5D8-4503-B7EC-3341354DF80A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"568bf645080bab7b22a369e1e1f5fc9097c4a6b0","datavalue":{"value":{"entity-type":"item","numeric-id":1818115,"id":"Q1818115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4376161$68DFFFFA-1FD4-4E6F-B2C8-22A8797297F7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4376161$721BB8DC-F90A-423B-88DF-887E00B22F0E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"548b8d016374fecee2380c0c1998212bc8be7020","datavalue":{"value":{"time":"+1998-02-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4376161$23A9EFA1-FAC0-4CB0-95E4-EE8E8A518C9F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4376161$99A63872-009C-4AC9-9D69-AD5813D9F129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4376161$8129C3DF-EBC8-40E3-825A-66ED76BA1FD5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e1ca75b427c9c9d6c652fd2b0d8687a283d9d4c4","datavalue":{"value":"1116350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4376161$93D435E3-7915-4067-83A1-A53F570EC518","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72c9d7764a367067a448fde498385822dabbbb28","datavalue":{"value":"\\(H\\)-decomposition of a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4376161$DD032D50-6DD0-4AB8-9EAF-0D4AC0E70A8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4376161$29B69A27-69DD-4488-91A7-D69A6505344E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c7efb33ab597088f6a738ee5884d6daad901c4d3","datavalue":{"value":"Q123215741","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4376161$62BB69D2-1360-46B8-90A0-210564D0BF92","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":"Q4376161$715C56A5-98D0-4B77-9548-CB2307834920","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fb1fc44c355e4b776efa927f8ae9776cafbda14a","datavalue":{"value":"https://doi.org/10.1137/s0097539792229507","type":"string"},"datatype":"url"},"type":"statement","id":"Q4376161$8C1AC6CB-13D5-4171-98EF-0D1FD949C340","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ae0cf5dd4f5310346c7c5e705163dfa39c765f0b","datavalue":{"value":"W1964448775","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4376161$71D04872-D3C8-486A-9871-7E49F37EEEE9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a64f2032be61bad2668ad77728b73313829a02d8","datavalue":{"value":{"entity-type":"item","numeric-id":1179032,"id":"Q1179032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29d79a13a85a777c2380256235d7042592e1efd1","datavalue":{"value":{"amount":"+0.93439746","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$B6338BDB-0F09-4FE2-8E18-37B2844D28B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b205b97e038ee4d5d30a2196f03bafc5025ab69","datavalue":{"value":{"entity-type":"item","numeric-id":1024436,"id":"Q1024436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37f73fbaf7eac0a12d55aa83a085285252e4ffc8","datavalue":{"value":{"amount":"+0.9023316","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$B9BF1D4D-65AC-406F-94BC-075635CF9E2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99b89cb05389986cb95ecffa3239daa481ff481e","datavalue":{"value":{"entity-type":"item","numeric-id":1423497,"id":"Q1423497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7307b9a6fbaf34f391ad9ea5061c266001a1bde4","datavalue":{"value":{"amount":"+0.8952912","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$6B896F75-984A-41F4-8AA0-8EAD7EAD8EF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d218b730217b5bca58349a65e856dd1a191a861","datavalue":{"value":{"entity-type":"item","numeric-id":4487664,"id":"Q4487664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5cc89a998a40704ae2b8a6c79acaab7bbabe54b","datavalue":{"value":{"amount":"+0.8869089","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$E68880C3-313B-4BAC-89C1-B25EA991B2BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4cfcdcf88d1afc8fd8ce1faecbbf37cf94397b6","datavalue":{"value":{"entity-type":"item","numeric-id":4498988,"id":"Q4498988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aebb09574c809252d0a7f818a5f729f2c1078f21","datavalue":{"value":{"amount":"+0.88168263","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$C53CA036-BFE0-4917-9EC5-D21328FF69F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72b3a8caf180fee1561a81c4c5bf9ffb698bd8d2","datavalue":{"value":{"entity-type":"item","numeric-id":1679321,"id":"Q1679321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b5c9304f87f4b1ba7fe27dc1e3ada124f2f29c8","datavalue":{"value":{"amount":"+0.87863076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$E9F5B3B0-80FF-4FD4-A0E3-B3E952B27AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0c13ee3a530a6cd0867e02adb1a28a21dd168ad","datavalue":{"value":{"entity-type":"item","numeric-id":1040837,"id":"Q1040837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9f4a561c5fd6200073f261b87da4d0ea272be76","datavalue":{"value":{"amount":"+0.8779713","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$C6B3C4C0-712A-49E7-995D-AAF0C4B61213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b5d68265ac7c6364fc4daf31c6e3e3c06b482ad","datavalue":{"value":{"entity-type":"item","numeric-id":5466029,"id":"Q5466029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6665f6fc212da9729429eaab419630745000774","datavalue":{"value":{"amount":"+0.8769985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$88FA1E84-DDD9-4798-B27A-E0088ADF9A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec704c45ae725c19ed2b6a26de7fedb7d0c91306","datavalue":{"value":{"entity-type":"item","numeric-id":3006095,"id":"Q3006095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71939b2166515dc5824214e56f5f37cc246fde6e","datavalue":{"value":{"amount":"+0.8763572","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4376161$33494787-453A-4F4F-B0A5-16703E31D5A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4376161","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4376161"}}}}}