Circular coloring of graphs via linear programming and tabu search

Bárány, Máté and Tuza, Zsolt (2015) Circular coloring of graphs via linear programming and tabu search. Central European Journal of Operations Research, 23 (4). pp. 833-848. ISSN 1435-246X

Text art_10.1007_s10100_014_0345_8_u.pdf Restricted to Registered users only Download (427kB) | Request a copy

Abstract

Circular coloring is a popular branch of graph theory which has been exhaustively studied for two decades mainly from a theoretical perspective. Since it is a refinement of the traditional proper coloring, it provides a more accurate model for cyclic scheduling problems which often arise in industrial applications. The present paper briefly surveys a special class of open shop scheduling that can be solved via circular coloring, and then proposes a new mathematical programming model and tabu search algorithm to compute the circular chromatic number of a graph effectively. © 2014 Springer-Verlag Berlin Heidelberg.

Actions (login required)

Edit Item