G-2006-16
On Edge Orienting Methods for Graph Coloring
, et référence BibTeX
We consider the problem of orienting the edges of a graph so that the length of a longest path in the resulting digraph is minimum. As shown by Gallai, Roy and Vitaver, this edge orienting problem is equivalent to finding the chromatic number of a graph. We study various properties of edge orienting methods in the context of local search for graph coloring. We then exploit these properties to derive four tabu search algorithms, each based on a different neighborhood. We compare these algorithms numerically to determine which are the most promising and to give potential research directions.
Paru en mars 2006 , 22 pages
Axe de recherche
Publication
jan. 2007
On edge orienting methods for graph coloring
, et
Journal of Combinatorial Optimization, 13(2), 163–178, 2007
référence BibTeX