{"entities":{"Q1847370":{"pageid":1858112,"ns":120,"title":"Item:Q1847370","lastrevid":69108390,"modified":"2026-04-13T04:50:20Z","type":"item","id":"Q1847370","labels":{"en":{"language":"en","value":"Deciding \\(k\\)-colorability in expected polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1835244"}},"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":"Q1847370$1CA01C36-009C-491D-BEC2-9B4C128C304E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c9d3fd588cbb74c0b6c8e2a338c409212f98a1b0","datavalue":{"value":{"text":"Deciding \\(k\\)-colorability in expected polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1847370$6C0BA1EA-D781-4D00-B1CA-26E5ADE54CEE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49d5b7c58491fbce4306e1a1be10ae064d0e07a5","datavalue":{"value":"1046.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1847370$C813D2A9-F08D-4C2F-B000-8CD1BF6AE33B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a24c8755abeb2891d098d6210ff77aeccb048ae1","datavalue":{"value":"10.1016/S0020-0190(01)00187-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1847370$5409C9B8-C650-41C3-BC3B-ABA87F149334","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$7476858C-B6FE-4683-9DFE-FB0D5EDE3102","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$5F049677-A3BA-4F54-B113-BCA53B374392","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8296cd667bfc66a2ed234dfa9a0d8644d49347aa","datavalue":{"value":{"time":"+2003-06-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":"Q1847370$833D9D43-B7FB-48F9-8646-70E471599343","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1847370$C2845893-9CCB-4F1B-977F-09AAEB87683A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"244032b7ebb2375b351e6b613bc7dfdfe4c94cba","datavalue":{"value":"1835244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1847370$30A59165-6F16-4185-A31E-20A62FA4F517","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":"Q1847370$3DF4D76B-39C3-4025-BCF1-AB00DCE1EBA7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"90997de5a829e0044ebc1b4791a319a07e124597","datavalue":{"value":{"entity-type":"item","numeric-id":1380939,"id":"Q1380939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$653B5FCA-D6B9-426C-BD68-FBAD71E95707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8da7825de31f293fb1233351445654b92201149f","datavalue":{"value":{"entity-type":"item","numeric-id":3736910,"id":"Q3736910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$FA2B6CDE-2974-4122-83F2-C9FAA1DD4D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6c6e30e71ec4191c814859d4ee8748fe67c73bf","datavalue":{"value":{"entity-type":"item","numeric-id":5903892,"id":"Q5903892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$FA3B44BA-F521-4119-875F-354756E94399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6de185ed34cee1497291c1163458e25bb1b1e9f2","datavalue":{"value":{"entity-type":"item","numeric-id":3031922,"id":"Q3031922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$D3D35CE1-23F5-429D-B7B9-77B83F392EE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c542e825a83e7cddf2484bd4a683e796049a82b","datavalue":{"value":{"entity-type":"item","numeric-id":4268434,"id":"Q4268434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$E41952F7-E93B-49A8-A8B3-BF6B5D44F39A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$0C6C7C34-D6C6-481A-A038-98CDBE2905EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f855246caf01e7d423da5ddcd02591be6660a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":4857375,"id":"Q4857375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$B8329040-9105-4DFE-832E-E9ED28D3E7E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de67154ac3679f10e545577bdf699216547737b3","datavalue":{"value":{"entity-type":"item","numeric-id":3841651,"id":"Q3841651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$8482B6D1-EBD8-4996-9FDE-F03C92FA4C3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$B61FED5B-03FF-4CFD-A602-09E4BAFDCAFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c9106d081c6999872e62f07a557038ab321eb17","datavalue":{"value":{"entity-type":"item","numeric-id":2754130,"id":"Q2754130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$A4B2E7D7-1541-44B1-9089-5D648D8A1C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdd51985f8df50c8dac6708d27413a9259a40295","datavalue":{"value":{"entity-type":"item","numeric-id":5905438,"id":"Q5905438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$7F59E386-EA27-48F0-8E10-53C84F8EC0A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2200a1a12c85fcfb7e26f8e0c137d4d7fd97f2b1","datavalue":{"value":{"entity-type":"item","numeric-id":4019373,"id":"Q4019373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$F3885415-220B-4511-903C-5ADC392BC707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f751e7e66ce1147b832025e94aab693980590ee","datavalue":{"value":{"entity-type":"item","numeric-id":794430,"id":"Q794430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1847370$3D9AE400-E1E0-4C61-BCCE-95E239D4CD41","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9c5ab18f934946604f2e896a2187fbdae8813979","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(01)00187-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1847370$17F58530-1F72-4A7A-9BB2-C6E5F7F9A296","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c761f7ba6816e6ec9a891481b744133fc227b803","datavalue":{"value":"W2007968698","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1847370$43AB636B-EC51-4CBC-A1C0-692D722DCF60","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f5ebe534ff667e12d1bd2e612254ef6c9b487b0","datavalue":{"value":{"entity-type":"item","numeric-id":4418675,"id":"Q4418675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdef814af15e577596cea6f07eb43f69131823ea","datavalue":{"value":{"amount":"+0.9079968","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":"Q1847370$927B2386-92AB-450C-BE2F-DB8D2A764A76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e1d6f43b4b35552e5bfa684aae44506b0f1ff61","datavalue":{"value":{"entity-type":"item","numeric-id":4708570,"id":"Q4708570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5e6537818eda81a1f844597e195f782f8afabdf","datavalue":{"value":{"amount":"+0.90587527","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":"Q1847370$9E1D90A8-224D-4928-9885-F1F522645E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a0a30195a5e3e1e16ab6941d9c916b749a15053","datavalue":{"value":{"entity-type":"item","numeric-id":5492855,"id":"Q5492855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"357c4f20fb54ab5eb3ab7389517a974928434b55","datavalue":{"value":{"amount":"+0.90417403","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":"Q1847370$FF11E04E-22FA-4F13-981B-F60C9CD21464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d490764b402dc36d39dd8df1ef32b3aaf5a7312","datavalue":{"value":{"entity-type":"item","numeric-id":6143974,"id":"Q6143974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75a6dcee8c9732ce79d8cd2e4809de2e88901ec1","datavalue":{"value":{"amount":"+0.9029998","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":"Q1847370$D4938348-7D56-4F2B-B14E-1247D7BAFB18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b7100c49cec0fc0f192ab67c6926171255b2693","datavalue":{"value":{"entity-type":"item","numeric-id":848637,"id":"Q848637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a34daf2cc917595e6201c9067b55fb0e5e9d64f0","datavalue":{"value":{"amount":"+0.90268445","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":"Q1847370$B611FB82-5AB8-4D54-A28E-633A74FB6F22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69e524e56114e8a331215f538fdeb8aafd0f5d4b","datavalue":{"value":{"entity-type":"item","numeric-id":2359789,"id":"Q2359789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e508e0b9b2936ee43217076ba23ebf6302d9344","datavalue":{"value":{"amount":"+0.9006747","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":"Q1847370$F2A30248-6841-4CEB-986E-B1981A54081D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89c945e01fc204a7c39cd185dab96002d1055e79","datavalue":{"value":{"entity-type":"item","numeric-id":1331989,"id":"Q1331989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"044c7d9aafe33ff8085de6b6754474263fa2f0c9","datavalue":{"value":{"amount":"+0.9004135","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":"Q1847370$90A0DCEA-7ADC-4F27-BDAF-8252EEDFA8E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"481800efe17b6acde89732ad76cbe9f583043ced","datavalue":{"value":{"entity-type":"item","numeric-id":5403058,"id":"Q5403058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"179c36aee7aa0f720b783e8ca5ca1f8160b4cc44","datavalue":{"value":{"amount":"+0.8963198","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":"Q1847370$F077A7AC-7D06-4472-9C2E-95BC2A2A98CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e15d8bd1cf908c806569804852297ce2d304017","datavalue":{"value":{"entity-type":"item","numeric-id":2851504,"id":"Q2851504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"179c36aee7aa0f720b783e8ca5ca1f8160b4cc44","datavalue":{"value":{"amount":"+0.8963198","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":"Q1847370$BA35311E-9997-4780-BF89-C38C48A15503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ab63dd900147c08dcd12dd1fc1d194aaa1c9639","datavalue":{"value":{"entity-type":"item","numeric-id":2636563,"id":"Q2636563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afdfb571ddf08830fbc0151c9e9fec3136d82baf","datavalue":{"value":{"amount":"+0.88647443","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":"Q1847370$35A673E5-D8D6-4155-88A4-782DFB3A4998","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deciding \\(k\\)-colorability in expected polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deciding_%5C(k%5C)-colorability_in_expected_polynomial_time"}}}}}