IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishGiven 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 |
Pubblicazioni consigliate
http://hdl.handle.net/2434/609821
Copyright © 2022