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) A column generation based algorithm for the robust graph coloring problem. Discrete Applied Mathematics, 217 (Part: ). pp. 340-352. ISSN 0166-218X (Print) 1872-6771 (Online)

This is the latest version of this item.

[thumbnail of 2017_DAM_Yuceogluetal_RobustColoring.pdf] PDF
Restricted to Registered users only

Download (460kB) | Request a copy


Given 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.
Item Type: Article
Uncontrolled Keywords: Robust graph coloring; Representatives formulation; Set-covering formulation; Column generation; Reduced cost fixing
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Güvenç Şahin
Date Deposited: 10 Sep 2017 18:22
Last Modified: 26 Apr 2022 09:50
URI: https://research.sabanciuniv.edu/id/eprint/33673

Available Versions of this Item

Actions (login required)

View Item
View Item