{"entities":{"Q659453":{"pageid":661302,"ns":120,"title":"Item:Q659453","lastrevid":63396852,"modified":"2026-04-11T12:37:09Z","type":"item","id":"Q659453","labels":{"en":{"language":"en","value":"Evaluating the effects of the clique selection in exact graph colouring algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5999219"}},"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":"Q659453$251C5ABE-D025-4800-9A82-EA0B7DFC49B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c82321e933037a12eb6e27094eb89badeea8f85","datavalue":{"value":{"text":"Evaluating the effects of the clique selection in exact graph colouring algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q659453$9026CAC0-E74A-410E-9FFD-1FB1EB67E545","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"93566c121b6f17cc324d4d766a5de6715f2192c9","datavalue":{"value":"1234.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659453$FA429826-7A34-4502-B010-D3FE01E55974","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a3090b100bb9da932f197119932720105fdf9470","datavalue":{"value":"10.1504/IJOR.2011.040696","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659453$7C74CB89-09B3-4CD8-9275-F2E320C549BE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2cdd1892625a16441d3991f7370b427d06f9bb5","datavalue":{"value":{"entity-type":"item","numeric-id":190512,"id":"Q190512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659453$A6EA1D57-CC5D-4D09-A0F9-338E3CAE8B67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05f8aaa1fcaa350ea29e602aa878272ced422c6b","datavalue":{"value":{"entity-type":"item","numeric-id":190513,"id":"Q190513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659453$3330F9DA-3717-4420-B702-550934CA07ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659453$030A393C-E7EC-4613-802F-39C793180B6B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"73f64ad09799a2b7c5e1e91e99e47c676c226996","datavalue":{"value":{"time":"+2012-01-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q659453$1F2ADF8A-2AFC-4F26-8B11-92EB49144A7F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a45e8883a62186ffca01ca4a3b5c7c2f3d7d5025","datavalue":{"value":"Summary: It is a common practice in exact enumerative algorithms for graph colouring to find a clique of maximum cardinality and to fix the colours of this subgraph before proceeding with implicit enumeration on the remainder of the graph. The goal of this experimental study is to analyse the effects on the enumeration process of some implementation issues related to the choice of such a clique. This paper is provided with experiments on random graphs and benchmarks.","type":"string"},"datatype":"string"},"type":"statement","id":"Q659453$C91DB296-5024-457E-93D3-F8F1AAA7256C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659453$5FF19409-12ED-4131-900A-5942873CF08D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659453$71B061B0-5941-4939-9D51-E38137495D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659453$33A0834D-55A8-4C86-9C46-2E095097169A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659453$D9AAA634-DD51-4333-9B7A-07D76526D963","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b5825a0b8e4e21989800c2067d2b9e223a252ab","datavalue":{"value":"5999219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659453$0CB32220-49E4-41E3-9791-7E31AB292E45","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ce0d6fd20f9080d625a240fed64cde089c3cb93","datavalue":{"value":"clique selection","type":"string"},"datatype":"string"},"type":"statement","id":"Q659453$7133FFCB-33CF-4EF3-B1BD-E62C6D69C14B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36c1cee00b0e24c100297a795ea9df96f04b4d0c","datavalue":{"value":"implicit enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q659453$C57568B9-D099-48A6-9FF2-82929AE1FB54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a61866b28ef67a30472e3ee08657696fe272f4","datavalue":{"value":"vertex colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q659453$11A436F6-25C9-46A6-A717-B43ADCAEAFF5","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":"Q659453$F2451C37-CC6A-45CA-9053-D8ED7257B14D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"966fe5a70b645fc5e08aea3f427addc0a3b7eaa5","datavalue":{"value":{"entity-type":"item","numeric-id":3757933,"id":"Q3757933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83566fec6fed740e2c4345d19d07b5dcb9b2171e","datavalue":{"value":{"amount":"+0.7931445837020874","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":"Q659453$94FB8625-C7C4-4465-B0CC-1919E600EA85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19c6c490df1da1f12b01a9f0c8be3452814ce320","datavalue":{"value":{"entity-type":"item","numeric-id":2257362,"id":"Q2257362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a47c81f28ec8196f6ac4cde7896c6b788f3bb859","datavalue":{"value":{"amount":"+0.7910874485969543","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":"Q659453$57A9EE5D-37E3-4793-B48E-0D0217BF4441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d07c9d5567c9b3dffebef1d8dc07db5210c4c4e3","datavalue":{"value":{"entity-type":"item","numeric-id":1671301,"id":"Q1671301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceae94fd275a883ab74ad42dc5d9cb184ccf2f58","datavalue":{"value":{"amount":"+0.7910537123680115","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":"Q659453$8B38D6BC-5AEA-479D-B47B-C165F0DB9681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a45cf0d8d67985971f9195d31c996e1fd0652e8a","datavalue":{"value":{"entity-type":"item","numeric-id":1736530,"id":"Q1736530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9950d07b74079120bf110b7e5772a081cc94f76","datavalue":{"value":{"amount":"+0.7909275889396667","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":"Q659453$15A268C0-E2F3-486A-940B-B6722D0512C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fc158c0594163dfb7df26e9a7ad792b28f7e549","datavalue":{"value":{"entity-type":"item","numeric-id":922964,"id":"Q922964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2acd95b406771f82791269b964985767f00e7b64","datavalue":{"value":{"amount":"+0.7856345772743225","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":"Q659453$E36633AA-2D19-44B2-89A3-675B6C8C8D51","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Evaluating the effects of the clique selection in exact graph colouring algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Evaluating_the_effects_of_the_clique_selection_in_exact_graph_colouring_algorithms"}}}}}