Scientific article

A graph coloring heuristic using partial solutions and a reactive tabu scheme

Published inComputers & operations research, vol. 35, p. 960-975
Publication date2008

Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called FOOPARTIALCOL), which is based on tabu search, considers feasible but partial solutions and tries to increase the size of the current partial solution. A solution consists of k disjoint stable sets (and, therefore, is a feasible, partial k-coloring) and a set of uncolored vertices. We introduce a reactive tabu tenure which substantially enhances the performance of both our heuristic as well as the classical tabu algorithm (called TABUCOL) proposed by Hertz and de Werra [Using tabu search techniques for graph coloring, Computing 1987;39:345–51].We will report numerical results on different benchmark graphs and we will observe that FOO-PARTIALCOL, though very simple, outperforms TABUCOL on some instances, provides very competitive results on a set of benchmark graphs which are known to be difficult, and outperforms the best-known methods on the graph flat300_28_0. For this graph, FOO-PARTIALCOL finds an optimal coloring with 28 colors. The best coloring achieved to date uses 31 colors. Algorithms very close to TABUCOL are still used as intensification procedures in the best coloring methods, which are evolutionary heuristics. FOO-PARTIALCOL could then be a powerful alternative. In conclusion FOO-PARTIALCOL is one of the most efficient simple local search coloring methods yet available.

  • Combinatorial optimization
  • Graph coloring
  • Tabu search
Citation (ISO format)
BLOECHLIGER, Ivo, ZUFFEREY, Nicolas. A graph coloring heuristic using partial solutions and a reactive tabu scheme. In: Computers & operations research, 2008, vol. 35, p. 960–975. doi: 10.1016/j.cor.2006.05.014
Main files (1)
Article (Published version)
ISSN of the journal0305-0548

Technical informations

Creation01/29/2013 11:34:00 AM
First validation01/29/2013 11:34:00 AM
Update time03/14/2023 8:01:26 PM
Status update03/14/2023 8:01:26 PM
Last indexation01/16/2024 1:08:30 AM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack