期刊
JOURNAL OF GLOBAL OPTIMIZATION
卷 59, 期 1, 页码 1-21出版社
SPRINGER
DOI: 10.1007/s10898-013-0075-9
关键词
Maximum clique problem; Branch and bound algorithm; Heuristic solution; Graph colouring
资金
- LATNA Laboratory, National Research University Higher School of Economics (NRU HSE), Russian Federation government [ag. 11.G34.31.0057]
- Program Research and development on priority directions of development of the scientific-technological complex of Russia [14.514.11.4065]
In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525-547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据