A survey of local search methods for graph coloring

A survey of local search methods for graph coloring

0.00 Avg rating0 Votes
Article ID: iaor20072560
Country: United Kingdom
Volume: 33
Issue: 9
Start Page Number: 2547
End Page Number: 2562
Publication Date: Sep 2006
Journal: Computers and Operations Research
Authors: ,
Keywords: graphs, heuristics: local search
Abstract:

Tabucol is a tabu search algorithm that tries to determine whether the vertices of a given graph can be colored with a fixed number k of colors such that no edge has both endpoints with the same color. This algorithm was proposed in 1987, one year after Fred Glover's article that launched tabu search. While more performing local search algorithms have now been proposed, Tabucol remains very popular and is often chosen as a subroutine in hybrid algorithms that combine a local search with a population based method. In order to explain this unfailing success, we make a thorough survey of local search techniques for graph coloring problems, and we point out the main differences between all these techniques.

Reviews

Required fields are marked *. Your email address will not be published.