A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
复制标题
DOI：
10.1007/978-3-642-11440-3_18
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
E. Tomita;Yoichi Sutani;Takanori Higashi;Shinya Takahashi;Mitsuo Wakatsuki
中科院分区：
文献类型：
--
作者：
E. Tomita;Yoichi Sutani;Takanori Higashi;Shinya Takahashi;Mitsuo Wakatsuki
本文提出了新的近似着色和其他相关技术，显著改善了分支定界算法MCR(J.Global Optim.，37，95-111,2007)的运行时间，该算法以前被证明是用于大量图的最快的最大团发现算法。通过在MCR中引入这些新技术而得到的算法称为MCS。实验结果表明，MCS算法能以较低的开销有效地减少搜索空间。大量的计算实验表明，MCS算法的计算速度明显快于MCR和其他已有算法。对于几个图，它比其他算法快一个数量级。特别是，对于密度非常高的困难图以及非常大和稀疏的图，即使MCS不是为任何特定类型的图设计的，它的速度也要快于MCR。对于某些极其密集的随机图，MCS可以比MCR快100,000倍以上。
This paper proposes new approximate coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, 95–111, 2007), previously shown to be the fastest maximum-clique-finding algorithm for a large number of graphs. The algorithm obtained by introducing these new techniques in MCR is named MCS. It is shown that MCS is successful in reducing the search space quite efficiently with low overhead. Consequently, it is shown by extensive computational experiments that MCS is remarkably faster than MCR and other existing algorithms. It is faster than the other algorithms by an order of magnitude for several graphs. In particular, it is faster than MCR for difficult graphs of very high density and for very large and sparse graphs, even though MCS is not designed for any particular type of graphs. MCS can be faster than MCR by a factor of more than 100,000 for some extremely dense random graphs.