Recycling Solutions for Vertex Coloring Heuristics

01/27/2019
by   Yasutaka Uchida, et al.
0

The vertex coloring problem is a well-known NP-hard problem and has many applications 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset