Recycling Solutions for Vertex Coloring Heuristics
Recycling Solutions for Vertex Coloring Heuristics
复制标题
DOI：
10.15807/jorsj.64.184
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Yasutaka Uchida;Kazuya Haraguchi
中科院分区：
文献类型：
--
作者：
Yasutaka Uchida;Kazuya Haraguchi
The vertex coloring problem is a well-known NP-hard problem and has many applications in operations research, especially in scheduling. A conventional approach to the problem solves the k-colorability problem iteratively, decreasing k one by one. Whether a heuristic algorithm finds a legal k-coloring quickly or not is largely affected by an initial solution. We propose a simple initial solution generator, the recycle method, which makes use of the legal (k+1)-coloring that has been found. An initial solution generated by the method is expected to guide a general heuristic algorithm to find a legal k-coloring quickly, as demonstrated by experimental studies. For example, TABUCOL, a conventional tabu search algorithm, achieves k=240 for the R1000.5 DIMACS graph when the recycle method is employed as the initial solution generator. This number cannot be attained by most state-of-the-art hybrid methods.
