A branch-and-price algorithm for the (k,c)-coloring problem

ENRICO MALAGUTI; ISABEL MÉNDEZ-DÍAZ; JUAN JOSÉ MIRANDA BRONT; PAULA ZABALA

NETWORKS

JOHN WILEY & SONS INC

Lugar: New York; Año: 2015 vol. 65 p. 353 - 366

0028-3045

In this article, we study the (k,c)-coloring problem, a generalization of the vertex coloring problem where we have to assign k colors to each vertex of an undirected graph, and two adjacent vertices can share at most c colors. We propose a new formulation for the (k,c)-coloring problem and develop a Branch-and-Price algorithm. We tested the algorithm on instances having from 20 to 80 vertices and different combinations for k and c, and compare it with a recent algorithm proposed in the literature. Computational results show that the overall approach is effective and has very good performance on instances where the previous algorithm fails.