Improvements to MCS algorithm for the maximum clique problem

Mikhail Batsyn (), Boris Goldengorin (), Evgeny Maslov () and Panos M. Pardalos ()
Additional contact information
Mikhail Batsyn: National Research University Higher School of Economics
Boris Goldengorin: National Research University Higher School of Economics
Evgeny Maslov: National Research University Higher School of Economics
Panos M. Pardalos: National Research University Higher School of Economics

Journal of Combinatorial Optimization, 2014, vol. 27, issue 2, No 14, 397-416

Abstract: Abstract In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast detection of clique vertices in a set of candidates, better initial colouring, and avoiding dynamic memory allocation. Our computational study shows some impressive results, mainly we have solved p_hat1000-3 benchmark instance which is intractable for MCS algorithm and got speedups of 7, 3000, and 13000 times for gen400_p0.9_55, gen400_p0.9_65, and gen400_p0.9_75 instances correspondingly.

Keywords: Maximum clique problem; Branch-and-bound algorithm; Heuristic solution; Graph colouring (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://link.springer.com/10.1007/s10878-012-9592-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:27:y:2014:i:2:d:10.1007_s10878-012-9592-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9592-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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