## A column generation based algorithm for the robust graph coloring problem
Yüceoğlu, Birol and Şahin, Güvenç and Van Hoesel, Stan C. P. M. (2017)
Official URL: http://dx.doi.org/10.1016/j.dam.2016.09.006 ## AbstractGiven an undirected simple graph G, an integer k, and a cost cij for each pair of non-adjacent vertices in G, a robust coloring of G is the assignment of k colors to vertices such that adjacent vertices get different colors and the total penalty of the pairs of vertices having the same color is minimum. The problem has applications in fields such as timetabling and scheduling. We present a new formulation for the problem, which extends an existing formulation for the graph coloring problem. We also discuss a column generation based solution method. We report computational study on the performance of alternative formulations and the column generation method.
## Available Versions of this Item- Robust graph coloring. (deposited 23 Dec 2015 14:59)
- A column generation based algorithm for the robust graph coloring problem. (deposited 29 Sep 2016 15:37)
- A column generation based algorithm for the robust graph coloring problem. (deposited 10 Sep 2017 18:22)
**[Currently Displayed]**
- A column generation based algorithm for the robust graph coloring problem. (deposited 10 Sep 2017 18:22)
- A column generation based algorithm for the robust graph coloring problem. (deposited 29 Sep 2016 15:37)
Repository Staff Only: item control page |