An adaptive memory algorithm for the k-coloring problem

Let G = (V, E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,..., k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms. (C) 2007 Elsevier B.V. All rights reserved.