Premium
Iterative coloring extension of a maximum clique
Author(s) -
Caramia Massimiliano,
Dell'Olmo Paolo
Publication year - 2001
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.1033
Subject(s) - complete coloring , combinatorics , mathematics , vertex (graph theory) , fractional coloring , upper and lower bounds , list coloring , clique problem , clique , induced subgraph , extension (predicate logic) , greedy coloring , graph coloring , graph , induced subgraph isomorphism problem , discrete mathematics , computer science , chordal graph , graph power , mathematical analysis , 1 planar graph , line graph , programming language , voltage graph
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 the 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. © 2001 John Wiley & Sons, Inc. Naval Research Logistic 48: 518–550, 2001