Iterative coloring extension of a maximum clique

Iterative coloring extension of a maximum clique

0.00 Avg rating0 Votes
Article ID: iaor20021928
Country: United States
Volume: 48
Issue: 6
Start Page Number: 518
End Page Number: 550
Publication Date: Sep 2001
Journal: Naval Research Logistics
Authors: ,
Keywords: programming: branch and bound
Abstract:

In this paper we present an improved branch and bound algorithm for the vertex coloring problem. The idea is to try to extend the coloring of a maximum clique to its adjacent vertices. If this succeeds, its successive neighbors are considered; in case of failure (i.e., in the case of initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optimal coloring of this subgraph by branch and bound. The process is repeated iteratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the maximum clique search, and a new method to compute upper bounds on subgraphs. Furthermore, a new branching rule and a method for the selection of the initial maximum clique are presented. Extensive computational results and comparisons with existing exact coloring algorithms on random graphs and benchmarks are given.

Reviews

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