Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1287/ijoc.1070.0245 | INFORMS Journal on Computing |
Keywords | Field | DocType |
computational result,postoptimization phase,adjacent vertex,overall algorithm,vertex coloring problem,evolutionary algorithm,best-known solution,high-quality solution,metaheuristic approach,dimacs instance,proposed algorithm,heuristics | Complete coloring,Discrete mathematics,Mathematical optimization,Combinatorics,Fractional coloring,Vertex (geometry),Evolutionary algorithm,Vertex (graph theory),Vertex cover,Feedback vertex set,Mathematics,Metaheuristic | Journal |
Volume | Issue | ISSN |
20 | 2 | 1091-9856 |
Citations | PageRank | References |
61 | 2.23 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Enrico Malaguti | 1 | 312 | 21.69 |
| Michele Monaci | 2 | 1049 | 60.78 |
| Paolo Toth | 3 | 215 | 10.79 |