Evaluating the effects of the clique selection in exact graph colouring algorithms

Evaluating the effects of the clique selection in exact graph colouring algorithms

0.00 Avg rating0 Votes
Article ID: iaor20116819
Volume: 11
Issue: 2
Start Page Number: 179
End Page Number: 192
Publication Date: Jun 2011
Journal: International Journal of Operational Research
Authors: ,
Keywords: experiment
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.