A New Genetic Graph Coloring Heuristic

Cornelius Croitoru, Henri Luchian, Ovidiu Gheorghies, Adriana Apetrei

To appear at Computational Symposium on Graph Coloring and Generalizations (COLOR02), Ithaca, NY, 7-8 September 2002


The aim of this paper is to introduce a new evolutionary formulation of the graph coloring problem, based on the interplay between orderings and colorings of vertices. The new formulation breaks symmetry in the solution space and provides opportunities for combining evolutionary and other search tehniques. Our formulation is very simple compared to previous approaches which use the relationship between a graph's chromatic number and its acyclic orientations. We outline an initial version of a Genetic Algorithm which implements this approach to the coloring problem. We summarise the results obtained from a set of systematic experiments; they provide convincing evidence that the new ordering approach can lead to accurate genetic coloring solvers, despite the contrary popular belief.

Server START Conference Manager
Update Time 23 Jul 2002 at 13:35:57
Maintainer trick@cmu.edu.
Start Conference Manager
Conference Systems