{"entities":{"Q3736910":{"pageid":5766816,"ns":120,"title":"Item:Q3736910","lastrevid":88708622,"modified":"2026-06-04T15:14:44Z","type":"item","id":"Q3736910","labels":{"en":{"language":"en","value":"A theoretical analysis of backtracking in the graph coloring problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3970114"}},"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":"Q3736910$91917226-4636-4154-9F83-3A9FEDC83A50","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"32e02bfa666342db8671b7e2b36fc1d328803748","datavalue":{"value":{"text":"A theoretical analysis of backtracking in the graph coloring problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3736910$6BC4B2EB-B2FA-4035-8304-54E8FE96BA71","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b25454ef2f29c919355d4ddaf4351d00cfeddf57","datavalue":{"value":"0601.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3736910$2B7930CE-8D4D-43F1-8D26-2CF7A87B546E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e6dd87693029bbe62615e4909200df2ddc236a1a","datavalue":{"value":"10.1016/0196-6774(85)90044-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3736910$D4AFCE25-2AC8-4308-83D2-DA0FCEFC5E24","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98974be3d76a16735c1235c5b39e5f8ca207c563","datavalue":{"value":{"entity-type":"item","numeric-id":585208,"id":"Q585208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3736910$C7D1D9A5-4D37-45F0-A9F2-8FC41B5CB215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bdba630e956e6c1e0d73d152d165d69bd88983b9","datavalue":{"value":{"entity-type":"item","numeric-id":648415,"id":"Q648415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3736910$D58A8C9D-6EC9-4304-B559-9F581CF1882F","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":"Q3736910$E9E9776E-559F-41A9-A25D-2D9166C36E98","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3736910$0516A9C1-76FC-49C2-8242-C713ADE7F1DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3736910$549CA2E5-2DFE-452A-9BAF-7ABD58863A12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3736910$0CDABA45-A8DB-4E3F-BA7B-7998BC4334AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3736910$2F1EE081-10B0-4C18-A974-252B8AF8E76D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ed6a097ae6431fd502c88b0069aac3550638de9e","datavalue":{"value":"3970114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3736910$F1ED7C1D-4693-4C3E-BAD7-DE342D4D28D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q3736910$24B64DD7-32AD-4DEA-8C96-D45AC5B7F82F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed19cce34a56bcc96a1fa41895faff2eb6292ba9","datavalue":{"value":"average behavior","type":"string"},"datatype":"string"},"type":"statement","id":"Q3736910$6F2B1BDA-A93E-4931-9E69-FD76077FA3CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63083ed32b92f2e7126824cf1b9ea1fb0b44b83e","datavalue":{"value":"run time distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q3736910$8BB2A859-8406-4C18-8AB3-F1E004DFCD03","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":"Q3736910$809AF104-5C38-46A9-AD44-1B17CEEA5AFA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2cf6a8a0a2a8c9424e35774ffcb9c1ec966c5b44","datavalue":{"value":"https://doi.org/10.1016/0196-6774(85)90044-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q3736910$6C9C2404-60EB-47E8-8C6E-ED487B1F4424","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2074bd4aa85ff05ef6f83dff20b1a428d486690a","datavalue":{"value":"W2043243657","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3736910$65CB7D92-258D-4964-B92B-2C06774AFDA6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56e46666a730b0de51f5e337db9f9e5555c9df2a","datavalue":{"value":{"entity-type":"item","numeric-id":794430,"id":"Q794430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"014df2e6bb925669fe45daa349c221b2c4d1df96","datavalue":{"value":{"amount":"+0.92671657","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":"Q3736910$77A884F7-CC7D-47A7-AAE7-34AAE3AE8FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1d38dac0578e05d149143085f1ae14c52fc2220","datavalue":{"value":{"entity-type":"item","numeric-id":3370783,"id":"Q3370783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93e7b61706497329ba32499c9d0102b6e09d202d","datavalue":{"value":{"amount":"+0.9221802","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":"Q3736910$C112383D-F15B-4ACF-8D12-CC86DB7B452E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d1dc8f3d16d3325ecf6a172b449cd812655038b","datavalue":{"value":{"entity-type":"item","numeric-id":2741266,"id":"Q2741266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2cc774fa2c90e0050276685145795e55da053fb","datavalue":{"value":{"amount":"+0.90025353","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":"Q3736910$41912E20-A1B7-496F-9D12-7E365525E30A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41087c15f21c6e0152adf7f531c5fc4b65b96cee","datavalue":{"value":{"entity-type":"item","numeric-id":2341776,"id":"Q2341776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4db7994a42103957bbb5c52198ab3abc128c59da","datavalue":{"value":{"amount":"+0.89561117","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":"Q3736910$C5939783-F9E9-4BDA-95BC-8FEF23CC8A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83f88d0b16cd0bd8b3094cdd8d9eba77ea725505","datavalue":{"value":{"entity-type":"item","numeric-id":477637,"id":"Q477637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8687b2ce3d55f10e9b2c2e0096ac63a2bc22548","datavalue":{"value":{"amount":"+0.89482737","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":"Q3736910$EECE36DA-0D89-4B4A-9ED5-633C38CD966D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cda6da1d1900f082819980df89238d75c55a9946","datavalue":{"value":{"entity-type":"item","numeric-id":434190,"id":"Q434190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29ca8231a95ad2e677ced8c4adadf8e7e1edeaef","datavalue":{"value":{"amount":"+0.8909687","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":"Q3736910$9A5EF961-A623-4BA0-A0F8-0F300C43A173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c2f1901f36e666659554ec59cc7e179ab2bafd2","datavalue":{"value":{"entity-type":"item","numeric-id":3424890,"id":"Q3424890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae865567a44a7e8a0971c2ff64872cc1486ed027","datavalue":{"value":{"amount":"+0.8899639","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":"Q3736910$81C155D1-2243-40FB-A4A8-AD033AE23267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bf764382d57d6ca995c41077c9dceec24f7c4be","datavalue":{"value":{"entity-type":"item","numeric-id":3312261,"id":"Q3312261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59bd3ad38bbd37604519cd3e3811d42ef5498cdc","datavalue":{"value":{"amount":"+0.88415897","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":"Q3736910$ED84445A-C557-487C-8E33-2E4BE61E0891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"141d29cd79b8fa0b8400ed99682eec5a952dc5cc","datavalue":{"value":{"entity-type":"item","numeric-id":497343,"id":"Q497343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10bc641b83bc0b486232b9b0b23f6b636f004a99","datavalue":{"value":{"amount":"+0.8806259","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":"Q3736910$BF830CBA-D73C-400F-8CD2-0748F215A169","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A theoretical analysis of backtracking in the graph coloring problem","badges":[]}}}}}