Speeding up branch and bound algorithms for solving the maximum clique problem

Evgeny Maslov, Mikhail Batsyn () and Panos Pardalos ()

Journal of Global Optimization, 2014, vol. 59, issue 1, 21 pages

Abstract: 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. Copyright Springer Science+Business Media New York 2014

Keywords: Maximum clique problem; Branch and bound algorithm; Heuristic solution; Graph colouring; 05C69; 05C85; 90C27; 90C59; 90-08 (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-013-0075-9 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:59:y:2014:i:1:p:1-21

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-013-0075-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().