An application of Iterated Local Search to Graph Coloring

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. In this article we explore the application of Iterated Local Search to the graph coloring problem. Iterated Local Search is a simple, yet powerful, metaheuristic that has shown very good results for a variety of optimization problems. In our research we investigate di#erent perturbation schemes and present computational results on some hard instances from the DIMACS benchmark suite.