Adaptive Memory Algorithms for Graph Coloring

Philippe Galinier Alain Hertz Nicolas Zufferey

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


Let G=(V,E) be a graph with vertex set V and edge set E. The graph coloring problem consists in assigning an integer (called color) to each vertex so that adjacent vertices get different colors, and the total number of different colors is minimized. The adaptive memory algorithm is an hybrid evolutionary heuristic based on a central memory. At each generation, the idea is to use the information of a central memory for producing an offspring which is then improved by using a local search algorithm. The so obtained solution is finally used to update the information contained in the memory. In this paper, we propose an adaptive memory algorithm to the graph coloring problem. The results obtained so far give evidence that our method is competitive with the best known coloring algorithms.

Server START Conference Manager
Update Time 23 Jul 2002 at 13:35:57
Start Conference Manager
Conference Systems