IEICE TRANSACTIONS on Information
A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.6 pp.1286-1298
- Publication Date
- 2013/06/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.1286
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Etsuji TOMITA
The University of Electro-Communications,JST ERATO Minato Discrete Structure Manipulation System Project,Tokyo Institute of Technology
Yoichi SUTANI
The University of Electro-Communications,Sony Corporation
Takanori HIGASHI
The University of Electro-Communications,Japan Systems Co., Ltd.
Mitsuo WAKATSUKI
The University of Electro-Communications,The University of Electro-Communications
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Etsuji TOMITA, Yoichi SUTANI, Takanori HIGASHI, Mitsuo WAKATSUKI, "A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 6, pp. 1286-1298, June 2013, doi: 10.1587/transinf.E96.D.1286.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1286/_p
Copy
@ARTICLE{e96-d_6_1286,
author={Etsuji TOMITA, Yoichi SUTANI, Takanori HIGASHI, Mitsuo WAKATSUKI, },
journal={IEICE TRANSACTIONS on Information},
title={A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments},
year={2013},
volume={E96-D},
number={6},
pages={1286-1298},
abstract={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.},
keywords={},
doi={10.1587/transinf.E96.D.1286},
ISSN={1745-1361},
month={June},}
Copy
TY - JOUR
TI - A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments
T2 - IEICE TRANSACTIONS on Information
SP - 1286
EP - 1298
AU - Etsuji TOMITA
AU - Yoichi SUTANI
AU - Takanori HIGASHI
AU - Mitsuo WAKATSUKI
PY - 2013
DO - 10.1587/transinf.E96.D.1286
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2013
AB - 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.
ER -
English
