TY - JOUR

T1 - A branch-and-price algorithm for the robust graph coloring problem

AU - Archetti, Claudia

AU - Bianchessi, Nicola

AU - Hertz, Alain

PY - 2014/3/11

Y1 - 2014/3/11

N2 - Given a graph G, an integer k, and a cost cuv associated with all pairs uv of non-adjacent vertices in G, the robust graph coloring problem is to assign a color in {1,.,k} to every vertex of G so that no edge has both endpoints with the same color, and the total cost of the pairs of vertices having the same color is minimum. We propose a branch-and-price algorithm for the solution of this problem. The pricing problem consists in finding a stable set of minimum total weight, and we propose both an exact and a heuristic algorithm for its solution. Computational experiments are reported for randomly generated and benchmark graph coloring instances.

AB - Given a graph G, an integer k, and a cost cuv associated with all pairs uv of non-adjacent vertices in G, the robust graph coloring problem is to assign a color in {1,.,k} to every vertex of G so that no edge has both endpoints with the same color, and the total cost of the pairs of vertices having the same color is minimum. We propose a branch-and-price algorithm for the solution of this problem. The pricing problem consists in finding a stable set of minimum total weight, and we propose both an exact and a heuristic algorithm for its solution. Computational experiments are reported for randomly generated and benchmark graph coloring instances.

KW - Branch-and-price algorithm

KW - Graph coloring

KW - Robust solution

KW - Tabu search

UR - http://www.scopus.com/inward/record.url?scp=84893729445&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893729445&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2013.02.013

DO - 10.1016/j.dam.2013.02.013

M3 - Article

AN - SCOPUS:84893729445

VL - 165

SP - 49

EP - 59

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -