{"entities":{"Q2931428":{"pageid":2942148,"ns":120,"title":"Item:Q2931428","lastrevid":44734263,"modified":"2025-11-25T14:55:12Z","type":"item","id":"Q2931428","labels":{"en":{"language":"en","value":"Linear degree extractors and the inapproximability of max clique and chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6373940"}},"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":"Q2931428$3ADCE3E4-6646-4354-9437-A6FBAD36E2A7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac3aae7f6ff36331d99da6fbe36e93bdd0521208","datavalue":{"value":{"text":"Linear degree extractors and the inapproximability of max clique and chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2931428$DF3D83CA-27A6-48EB-B168-5FDD88FD5D62","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cc7c5d825a21ba40a204653438b09bb302980989","datavalue":{"value":"1301.68152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$7A60DC2D-531C-4A02-ADA3-B724005E6340","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"053d38bf6da50265ae1da6d65398dc29650850f5","datavalue":{"value":"10.1145/1132516.1132612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$4341F127-E9A3-4DBC-BBF4-5111882F0FD8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"11e9247244d7c5a83ff00535a80d8b3489fb0336","datavalue":{"value":{"entity-type":"item","numeric-id":294713,"id":"Q294713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2931428$CF282AD5-7588-4122-8DCC-67861AF159E7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"54059bc97ea0b59891d0757630d22c65e6728847","datavalue":{"value":{"entity-type":"item","numeric-id":2931363,"id":"Q2931363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2931428$69ED3A4C-EC43-42FD-B340-38C58C7E8D94","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a882446bd128890a95a71deebb9cb2548da37a94","datavalue":{"value":{"time":"+2014-11-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2931428$C841416C-F95E-46AA-AFB4-01CFE270E99E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$4AA5293F-EC4C-454A-8D4E-60E01421C6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$007695C0-FB3C-4834-BD37-CD4C7654CE4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$A67D2E3C-724A-4D67-9385-0DCA8744FFC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4bceb4852f142c7ae840ef027a3d11ea672a1bc4","datavalue":{"value":"11B75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$5A52AC05-732C-4E01-B85F-5234AA247BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$7FA1575B-8BBD-47FD-B5DE-FB7056347405","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"584155bd733df621ca5e6835fd2766b9db199594","datavalue":{"value":"6373940","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$F37F8D62-D46B-4C66-8CC3-E01F96FC1108","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q2931428$98A87CD7-88EF-4BC4-AE4D-9DEFA674F773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2931428$DFFE2B86-49FA-413A-BF00-5C8073A79A55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2931428$AE7892E7-8C65-4851-8755-2AE20B524996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q2931428$F9F2B035-7664-42A4-AC52-9B32DE8830F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d06ce36e382a1222c0d25591134f593d41cb28c5","datavalue":{"value":"disperser","type":"string"},"datatype":"string"},"type":"statement","id":"Q2931428$D897D882-5101-4B26-8B6B-78C433994C68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7557a7948f6fd7a15949a6211d80d29e3293181c","datavalue":{"value":"explicit construction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2931428$94A054F5-576D-4581-AC01-869181BDE26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c011d2c06f8952f6e94e6ef026746e90647f36f2","datavalue":{"value":"extractor","type":"string"},"datatype":"string"},"type":"statement","id":"Q2931428$D330AB84-79C3-41B3-9842-171F3EF2B4AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b44d3f732cb50abf873f800603732c6d83137fb","datavalue":{"value":"pseudorandom","type":"string"},"datatype":"string"},"type":"statement","id":"Q2931428$FA654338-4648-4B3B-B259-511727ED1BD9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e2b8dbe8a2e7931a02b7bd33e7daffb003dce092","datavalue":{"value":"Q56210451","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$ED6FBE67-C6BA-4A93-B6F2-F66548E35785","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":"Q2931428$E976263E-9CDE-4B9B-B2D4-F816C6DAEB9D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c878f959f6cf2b92ff40ff29fc6d16547feb530","datavalue":{"value":"https://doi.org/10.1145/1132516.1132612","type":"string"},"datatype":"url"},"type":"statement","id":"Q2931428$1AC60E47-AE17-4CA5-83D1-EF143B0B10AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4263e77cdbddd95317d2ac70a401600ee17d1c83","datavalue":{"value":"W2126186592","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2931428$3DD641F0-A971-4166-8880-76A805AB20B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"103e3d5e562b215b40dd07c21d1a8b44b9ed8460","datavalue":{"value":{"entity-type":"item","numeric-id":3002782,"id":"Q3002782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","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":"Q2931428$5D6FA7E7-8C3C-44F2-91DC-44A52BB98F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc5c70de174e7b02d7d9415615151d458cd8f461","datavalue":{"value":{"entity-type":"item","numeric-id":3613762,"id":"Q3613762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"815b4809839a55c99e120c0915f64af69866f24b","datavalue":{"value":{"amount":"+0.88405323","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":"Q2931428$FA5922CA-587D-4C71-912F-AD06B2EAE03E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"691283aad9612448def822d46ffe3cacc9a3dc72","datavalue":{"value":{"entity-type":"item","numeric-id":342100,"id":"Q342100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3e7d4406246fca6f23e49f77b686f11950a670f","datavalue":{"value":{"amount":"+0.86852443","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":"Q2931428$0EDD7CD3-DFAD-4049-970A-9D14C3303068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1c9fae3fbb603373c87d66ca5cfc2eb1bdee893","datavalue":{"value":{"entity-type":"item","numeric-id":3020016,"id":"Q3020016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c560b95c36bfbf00c90d62c2add9037d2d138638","datavalue":{"value":{"amount":"+0.86352265","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":"Q2931428$74C69668-D675-4155-A869-5B5EC9B046B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abff7155f277691234460bb6c08c44232bb10456","datavalue":{"value":{"entity-type":"item","numeric-id":1874411,"id":"Q1874411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"126518038f2e0b149ede3aeb812769f6f18c33c3","datavalue":{"value":{"amount":"+0.8622485","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":"Q2931428$BBBBF02C-FCC2-407F-93BB-477FE699A6C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"480ba3294073f6f2b4ce9264144d74039e0d2b6c","datavalue":{"value":{"entity-type":"item","numeric-id":2851436,"id":"Q2851436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e25c5aa7bc202740546665d6d64b8bc11f8db44b","datavalue":{"value":{"amount":"+0.86224777","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":"Q2931428$AF1E4C04-B2DA-46BB-BB86-FDDFA8EB120A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcc36a25065887d8410bd1819a994197165080f5","datavalue":{"value":{"entity-type":"item","numeric-id":626759,"id":"Q626759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23b032208291489564e58e111b21902241837716","datavalue":{"value":{"amount":"+0.8590702","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":"Q2931428$DC19A122-F2DF-4FDD-ABB1-F22DA65AB89F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27354edb5bf0bbb0ac053d60faffa3f9ba88f2d5","datavalue":{"value":{"entity-type":"item","numeric-id":1877696,"id":"Q1877696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d05694f8036a738a82124944b36d82390e025c2","datavalue":{"value":{"amount":"+0.8585911","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":"Q2931428$8AACF8C4-C8CC-4608-80CC-24AFD0075DD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc355d7102e4be85902ec346c15e4db519ba5386","datavalue":{"value":{"entity-type":"item","numeric-id":287036,"id":"Q287036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83b19f58d2438d8a2c3b95933ac4db3e42717dbc","datavalue":{"value":{"amount":"+0.8582177","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":"Q2931428$D2AF9944-BAA9-4681-A1CB-711A3A8A7CA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06cc96dfac8e1b559c17bc6645b617c39a1b8134","datavalue":{"value":{"entity-type":"item","numeric-id":3449868,"id":"Q3449868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27ada968fcf1bec792e726dfdb51debfeeb614ac","datavalue":{"value":{"amount":"+0.856858","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":"Q2931428$CFD8D836-07BA-47E3-BD68-F8FD6E505A90","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2931428","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2931428"}}}}}