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.
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.
Titolo: | A branch-and-price algorithm for the robust graph coloring problem |
Autori: | |
Parole Chiave: | Graph coloring; Robust solution; Branch-and-price algorithm; Tabu search |
Settore Scientifico Disciplinare: | Settore MAT/09 - Ricerca Operativa |
Data di pubblicazione: | 2014 |
Rivista: | |
Tipologia: | Article (author) |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.dam.2013.02.013 |
Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
A-branch-and-price-algorithm-for-the-robust-graph-coloring-problem_DAM-13.pdf | Publisher's version/PDF | Administrator Richiedi una copia |