Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
476212 | Computers & Operations Research | 2006 | 16 Pages |
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 kk 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Philippe Galinier, Alain Hertz,