Graph Coloring Problems
Graph Coloring Problems
复制标题
DOI：
10.1002/9781118600207.ch10
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
D. de Werra;D. Kobler
中科院分区：
文献类型：
--
作者：
D. de Werra;D. Kobler
本章介绍了着色的基本概念，以及由于各种调度问题（包括制定学校时间表）而引起的一系列变化和概括。给出了基于禁忌搜索的求解大型问题近似解的方法概要。禁忌算法的另一个优点是它相对容易适应各种图着色问题。由于精确着色算法的简单性，完全可序图类在着色方面很有趣。对于任意图的着色问题通常是困难的，而完美图类具有包含可在多项式时间内计算出色数的图的特殊性。本章开头给出的调度问题，如果用图着色的形式表述，就属于色调度的范畴。
This chapter presents the basic concepts of colorings as well as a series of variations and generalizations prompted by various scheduling problems including drawing up school timetables. It gives an outline of methods based on the Tabu search for finding approximate solutions for large problems. An additional advantage of the Tabu algorithm is that it is relatively easy to adapt it to various graph coloring problems. The class of perfectly orderable graphs is interesting with regard to coloring because of the simplicity of the exact coloring algorithm. While coloring problems are generally hard for arbitrary graphs, the class of perfect graphs has the particularity of containing graphs for which the chromatic number can be calculated in polynomial time. When formulated in terms of graph coloring, the scheduling problem given at the beginning of the chapter belongs to the domain of chromatic scheduling.