Bounding vertex coloring by truncated multistage branch and bound
Bounding vertex coloring by truncated multistage branch and bound
复制标题
通过截断的多级分支定界进行边界顶点着色
DOI：
10.1002/net.20035
复制
发表时间：
2004
期刊：
影响因子：
2.1
通讯作者：
P. Dell’Olmo
中科院分区：
文献类型：
--
作者：
M. Caramia;P. Dell’Olmo
在这篇文章中，我们设计了一个截断枚举算法的基础上，分支和边界规则嵌入在一个多级计划，允许迭代访问的子图。该算法的目的是找到下界的图的色数，并通过简单的着色扩展规则，它往往是能够找到最佳的解决方案。在这个问题上，我们得到了一个非常有希望的结果：我们的算法能够解决以前没有解决过的基准DSJC 125_5，DSJC 125_9，DSJC 250_1，DSJR 500_1c和DSJR 500_5。此外，我们展示了如何我们的方法可以用来寻找上界的色数，因此，我们比较的上界，下界的差距，使已知的精确算法实现。比较结果表明，在超过一半的测试基准测试中，我们的算法获得的差距差距低于最近的分支和切割方法以及著名的DSATU算法。为了提供更深入的分析，我们最后比较了所提出的算法在相同的基准上发现的最佳启发式解决方案在公开文献。此外，在这种情况下，所提出的截断分支和界限往往能够优于这些启发式解决方案。© 2004 Wiley Periodicals，Inc. NETWORKS，Vol. 44（4），231-242 2004
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