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

Variable space search for graph coloring

Hertz, Alain
Plumettaz, Matthieu
Published in Discrete Applied Mathematics. 2008, vol. 156, p. 2551-2560
Abstract Let G = (V, E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1, ..., k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the k-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The k-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms.
Keywords Graph coloringLocal searchVariable space search
Full text
Article (Published version) (606 Kb) - document accessible for UNIGE members only Limited access to UNIGE
(ISO format)
HERTZ, Alain, PLUMETTAZ, Matthieu, ZUFFEREY, Nicolas. Variable space search for graph coloring. In: Discrete Applied Mathematics, 2008, vol. 156, p. 2551-2560. https://archive-ouverte.unige.ch/unige:26171

136 hits

0 download


Deposited on : 2013-02-04

Export document
Format :
Citation style :