Year
2014
Authors
ARCHETTI Claudia, BIANCHESSI Nicola, HERTZ Alain
Abstract
Given a graph , an integer , and a cost associated with all pairs of non-adjacent vertices in , the robust graph coloring problem is to assign a color in to every vertex of 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.
ARCHETTI, C., BIANCHESSI, N. et HERTZ, A. (2014). A branch-and-price algorithm for the robust graph coloring problem. Discrete Applied Mathematics, 165, pp. 49-59.