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 present an exact algorithm for the solution of VCP based on the well-known Set Covering formulation of the problem. We propose a Branch-and-Price algorithm embedding an effective heuristic from the literature and some methods for the solution of the slave problem, as well as two alternative branching schemes. Computational experiments on instances from the literature show the effectiveness of the algorithm, which is able to solve, for the first time to proven optimality, five of the benchmark instances in the literature, and reduce the optimality gap of many others.

An Exact Approach for the Vertex Coloring Problem

MONACI, MICHELE;
2011

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 present an exact algorithm for the solution of VCP based on the well-known Set Covering formulation of the problem. We propose a Branch-and-Price algorithm embedding an effective heuristic from the literature and some methods for the solution of the slave problem, as well as two alternative branching schemes. Computational experiments on instances from the literature show the effectiveness of the algorithm, which is able to solve, for the first time to proven optimality, five of the benchmark instances in the literature, and reduce the optimality gap of many others.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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: https://hdl.handle.net/11577/150646
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 96
  • ???jsp.display-item.citation.isi??? 80
  • OpenAlex ND
social impact