Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs

Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs

0.00 Avg rating0 Votes
Article ID: iaor20002941
Country: United States
Volume: 1
Issue: 1
Start Page Number: 105
End Page Number: 128
Publication Date: Jan 1995
Journal: Journal of Heuristics
Authors: , ,
Keywords: heuristics
Abstract:

We present in this article an evolutionary procedure for solving general optimization problems. The procedure combines efficiently the mechanism of a simple descent method and of genetic algorithms. In order to explore the solution space properly, periods of optimization are interspersed with phases of interaction and diversification. An adaptation of this search principle to coloring problems in graphs is discussed. More precisely, given a graph G, we are interested in finding the largest induced subgraph of G that can be colored with a fixed number q of colors. When q is larger or equal to the chromatic number of G then the problem amounts to finding an ordinary coloring of the vertices of G.

Reviews

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