Premium
Bounding vertex coloring by truncated multistage branch and bound
Author(s) -
Caramia Massimiliano,
Dell'Olmo Paolo
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20035
Subject(s) - bounding overwatch , branch and bound , vertex (graph theory) , combinatorics , fractional coloring , computer science , upper and lower bounds , mathematics , graph , algorithm , artificial intelligence , mathematical analysis , line graph , graph power
In this article we design a truncated enumerative algorithm based on branch and bound rules embedded in a multistage scheme that allows iterative visits of subgraphs. The algorithm is designed to find lower bounds on the chromatic number of graphs, and, by means of simple coloring extension rules, it is often capable of finding optimal solutions. In this issue we obtain a very promising result: our algorithm was able to solve benchmarks DSJC125_5, DSJC125_9, DSJC250_1, DSJR500_1c, and DSJR500_5, which had not previously been solved. Furthermore, we show how our method can be employed in finding upper bounds on the chromatic number, and thus, we compare the upper bound–lower bound gaps so obtained with those achieved by known exact algorithms. The comparison highlights that in more than half of the tested benchmarks the gap obtained by our algorithm was lower than that obtained by a recent branch and cut method and by the well‐known DSATUR algorithm. To provide a deeper analysis we finally compare the upper bounds found by the proposed algorithm on the same benchmarks with the best heuristic solutions known in the open literature. Also, in this case, the proposed truncated branch and bound was often able to outperform these heuristic solutions. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 231–242 2004