A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments
A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments
复制标题
DOI：
10.1587/transinf.e96.d.1286
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
E. Tomita;Yoichi Sutani;Takanori Higashi;Mitsuo Wakatsuki
中科院分区：
文献类型：
--
作者：
E. Tomita;Yoichi Sutani;Takanori Higashi;Mitsuo Wakatsuki
总结许多问题可以作为最大的集团问题。且结合算法MCR（J. Global Optim。，37，pp.95–111，2007），以前证明是大量最大最大发现算法最快的算法图尤其是几个图的数量级，它比其他算法更快。尽管MC的设计并不比MCR更快，但对于非常大的MC而言，对于非常大的MC而言，非常高的密度和稀疏图。 MCS中每种新技术的有效性以及总体贡献。
SUMMARY Many problems can be formulated as maximum clique problems. Hence, it is highly important to develop algorithms that can find a maximum clique very fast in practice. We propose new approximate coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, pp.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. Extensive computational experiments confirm the superiority of MCS over MCR and other existing algorithms. It is faster than the other algorithms by orders 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 graph. MCS can be faster than MCR by a factor of more than 100,000 for some extremely dense random graphs. This paper demonstrates in detail the effectiveness of each new techniques in MCS, as well as the overall contribution.