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

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

0.00 Avg rating0 Votes
Article ID: iaor20091328
Country: United Kingdom
Volume: 35
Issue: 3
Start Page Number: 960
End Page Number: 975
Publication Date: Mar 2008
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics: tabu search
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.

Reviews

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