Data di Pubblicazione:
2014
Citazione:
A branch-and-price algorithm for the robust graph coloring problem / C. Archetti, N. Bianchessi, A. Hertz. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 165(2014), pp. 49-59.
Abstract:
Given a graph G, an integer k, and a cost c(u,v) associated with all pairs (u,v) 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.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Graph coloring; Robust solution; Branch-and-price algorithm; Tabu search
Elenco autori:
C. Archetti, N. Bianchessi, A. Hertz
Link alla scheda completa: