
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Simple and Faster BranchandBound Algorithm for Finding a Maximum Clique with Computational Experiments
Etsuji TOMITA Yoichi SUTANI Takanori HIGASHI Mitsuo WAKATSUKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E96D
No.6
pp.12861298 Publication Date: 2013/06/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E96.D.1286
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: maximum clique, branchandbound, approximate coloring, computational experiments,
Full Text: PDF(791.5KB)>>
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 branchandbound algorithm MCR (J. Global Optim., 37, pp.95–111, 2007), previously shown to be the fastest maximumcliquefinding 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.

