Retour aux résultats
Articles (2014), Discrete Applied Mathematics, 165, pp. 49-59

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

ARCHETTI Claudia , Bianchessi Nicola, Hertz Alain

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. Lien vers l'article

ARCHETTI, C., BIANCHESSI, N. and HERTZ, A. (2014). A branch-and-price algorithm for the robust graph coloring problem. Discrete Applied Mathematics, 165, pp. 49-59.

Mots clés : #Graph-coloring, #Robust-solution, #Branch, #and, #price-algorithm, #Tabu-search