A Metaheuristic Approach for the Vertex Coloring Problem
Enrico Malaguti, Michele Monaci, Paolo Toth
INFORMS Journal on Computing · 2008 · Volume 20 · Issue 2
Abstract
Given an undirected graph G = ( V, E ), the vertex coloring problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. In this paper, we propose a metaheuristic approach for VCP that performs two phases: the first phase is based on an evolutionary algorithm, whereas the second one is a postoptimization phase based on the set covering formulation of the problem. Computational results on a set of DIMACS instances show that the overall algorithm is able to produce high-quality solutions in a reasonable amount of time. For four instances, the proposed algorithm is able to improve the best-known solution while for almost all the remaining instances, it finds the best-known solution in the literature.
Keywords
evolutionary algorithm, set covering, heuristics
Enable JavaScript for citation tools and additional paper interactions.