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.

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

N. Bianchessi;
2014

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.
Graph coloring; Robust solution; Branch-and-price algorithm; Tabu search
Settore MAT/09 - Ricerca Operativa
2014
Article (author)
File in questo prodotto:
File Dimensione Formato  
A-branch-and-price-algorithm-for-the-robust-graph-coloring-problem_DAM-13.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 445.3 kB
Formato Adobe PDF
445.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/609821
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 9
social impact