Recycling Solutions for Vertex Coloring Heuristics

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.

Knowledge Graph



Sign up or login to leave a comment