UNIGE document Scientific Article
previous document  unige:26173  next document
add to browser collection

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

Bloechliger, Ivo
Published in Computers & Operations Research. 2008, vol. 35, p. 960-975
Abstract 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.
Keywords Combinatorial optimizationGraph coloringTabu search
Full text
Article (Published version) (185 Kb) - document accessible for UNIGE members only Limited access to UNIGE
(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 https://archive-ouverte.unige.ch/unige:26173

398 hits

0 download


Deposited on : 2013-02-04

Export document
Format :
Citation style :