An application of Iterated Local Search to Graph Coloring Problem

Marco Chiarandini and Thomas Stuetzle

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


Abstract

Graph coloring is a well known problem from graph theory that, when solving it with local search algorithms, is typically treated as a series of constraint satisfaction problems: for a given number of colors k, one has to find a feasible coloring; once such a coloring is found, the number of colors is decreased and the local search starts again. Here we explore the application of Iterated Local Search to the graph coloring problem. Iterated Local Search is a simple and powerful metaheuristic that has shown very good results for a variety of optimization problems. In our research we investigate different perturbation schemes and present computational results on some hard instances from the DIMACS benchmark suite.


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