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

Authors: Massimiliano Caramia, Paolo Dell'Olmo

Addresses: Dipartimento di Ingegneria dell'Impresa, University of Rome 'Tor Vergata', Via del Politecnico, Rome 1 – 00133, Italy. ' Dipartimento di Statistica, Probabilita e Statistiche Applicate, University of Rome 'La Sapienza', Piazzale Aldo Moro, Rome 5 – 00185, Italy

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.

Keywords: clique selection; implicit enumeration; vertex colouring; graph colouring; random graphs; benchmarks.

DOI: 10.1504/IJOR.2011.040696

International Journal of Operational Research, 2011 Vol.11 No.2, pp.179 - 192

Published online: 16 Jun 2011 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article