On edge orienting methods for graph coloring

详细信息    查看全文

• 作者：Bernard Gendron ; Alain Hertz and Patrick St-Louis
• 关键词：Graph coloring ; Local search ; Edge orienting
• 刊名：Journal of Combinatorial Optimization
• 出版年：2007
• 出版时间：February, 2007
• 年：2007
• 卷：13
• 期：2
• 页码：163-178
• 全文大小：513 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

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.