{"entities":{"Q4939608":{"pageid":6969190,"ns":120,"title":"Item:Q4939608","lastrevid":91769162,"modified":"2026-06-05T00:01:20Z","type":"item","id":"Q4939608","labels":{"en":{"language":"en","value":"Minimum Coloring k-Colorable Graphs in Polynomial Average Time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1400084"}},"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":"Q4939608$BC42C36E-818A-486F-9459-7861C57BAC6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6f2cab36fb12e9a578c7c6c10f4b179e96ee11f1","datavalue":{"value":{"text":"Minimum Coloring k-Colorable Graphs in Polynomial Average Time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4939608$0C45B68A-59FF-4034-A593-7C53E8049EAA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bb929693e93484b0448e07734e5cd3fd04ee8d5b","datavalue":{"value":"0938.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4939608$04E298C1-9FD7-4EFB-BFB2-A38E490DD830","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"119fbbf23967ffad7b319a3cca84803ae6be69b0","datavalue":{"value":{"entity-type":"item","numeric-id":536213,"id":"Q536213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4939608$06F78E6A-EDD4-4853-ABD1-2CFB7ED7680D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9bcfebe9d23b7752651008b0d843e08ec7c57a37","datavalue":{"value":{"entity-type":"item","numeric-id":2709787,"id":"Q2709787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4939608$34C43528-7171-4B5D-9312-3E767885D23F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"06866b48a786ed155357714aef89ff09a5a66e91","datavalue":{"value":{"time":"+2000-03-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4939608$6590DBE4-06D4-41F6-AEA2-57DAF3DF2EBF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4939608$A0CC17CA-47BE-4292-9428-85B6100F2351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4939608$23DC9CFA-D66C-4373-BF6C-0DBEFD7D2EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4939608$EBD75AD7-DA61-4F63-8486-37FE7E33024F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"effaa68d91c73ea1ea88f675e0cf681d1c8bb299","datavalue":{"value":"1400084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4939608$214E694C-3FDD-4770-A21B-870FD06305D8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q4939608$D41CCBFE-C44D-4040-ABB4-DEB3C614FB88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q4939608$FBC280B9-FF39-4088-B7CE-B2B7200582FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4939608$859C97C8-8C75-4A9D-BDF2-C7EA17281160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q4939608$A9A5E214-4F9F-4F5F-A936-8BFB664AF835","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":"Q4939608$986DC529-6487-4413-A6C8-E6B14A27875F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f6a7131d05ca972a61cd7d132e717bd5cd1fffff","datavalue":{"value":"https://doi.org/10.1006/jagm.1999.1035","type":"string"},"datatype":"url"},"type":"statement","id":"Q4939608$806952FA-5058-496D-A4CE-FDAC9CC28EF9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"444728a7e77e4f17b9ea008e1c24f26cff30c52a","datavalue":{"value":"W2006269066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4939608$67432BF6-1EB5-41F2-A57F-FC22C7DA3694","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9d773d46a99709e2210e7e211d6a986a2a51b600","datavalue":{"value":"10.1006/JAGM.1999.1035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4939608$94872045-1DA2-4EE1-BC9A-C2B58C8EDAB8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c60cf3fec234e04da451cb1f6249a44d76ae1d5","datavalue":{"value":{"entity-type":"item","numeric-id":4705329,"id":"Q4705329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3cd1331e57576ceed1051400d2234bde5a51320","datavalue":{"value":{"amount":"+0.9011371731758118","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":"Q4939608$A1AF7B83-8AB6-4C48-83E6-E0BABAD58E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe9dd2dc8982d15630c4c015d3f3740d444f04e8","datavalue":{"value":{"entity-type":"item","numeric-id":5466478,"id":"Q5466478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84ec8eec5d2a96dc61b176fde41cc89b87e25af6","datavalue":{"value":{"amount":"+0.8924302458763123","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":"Q4939608$605B372F-45A7-4D7B-B2F4-90FA4F71B8B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cdb463fd488f1192c264c9eec3865672a2fd533","datavalue":{"value":{"entity-type":"item","numeric-id":5437231,"id":"Q5437231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a0a17759314fa30a405648346767f8120e456aa","datavalue":{"value":{"amount":"+0.8706485629081726","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":"Q4939608$A834ED65-8B94-430C-B53A-6AFFCFB8B014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ee13911828129a17e83c61562cea4f44e26d940","datavalue":{"value":{"entity-type":"item","numeric-id":5056148,"id":"Q5056148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"293b090f501d56476fd8db29149f42845b8e2b55","datavalue":{"value":{"amount":"+0.8689903616905212","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":"Q4939608$85E8CBA8-31FC-4B1F-AF75-E507A16944F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec4ee876f395489e81c7bec37638860005478728","datavalue":{"value":{"entity-type":"item","numeric-id":4948046,"id":"Q4948046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e41d8d972e184d0d0dddc1e5615265f7d56ea8a5","datavalue":{"value":{"amount":"+0.8674418926239014","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":"Q4939608$D6C06119-0841-4698-948D-1FBBA6505D1D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum Coloring k-Colorable Graphs in Polynomial Average Time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_Coloring_k-Colorable_Graphs_in_Polynomial_Average_Time"}}}}}