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 mini- mized. 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 over- all 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.

A Metaheuristic Approach for the Vertex Coloring Problem

MALAGUTI, ENRICO;MONACI, MICHELE;TOTH, PAOLO
2008

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 mini- mized. 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 over- all 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.
E. Malaguti; M.Monaci; P.Toth
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/63531
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 90
  • ???jsp.display-item.citation.isi??? 69
social impact