Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements

DOI10.1007/978-1-4614-8588-9_7zbMath1344.90063OpenAlexW15861619MaRDI QIDQ2820111

Evgeny Maslov, Mikhail Batsyn, Panos M. Pardalos

Publication date: 13 September 2016

Published in: Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4614-8588-9_7

zbMATH Keywords

graph coloringmaximum clique problemILS heuristicMCS branch-and-bound algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On comparing algorithms for the maximum clique problem

Uses Software

• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast local search for the maximum independent set problem
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• Greedy randomized adaptive search procedures
• A hybrid heuristic for the maximum clique problem
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Large Cliques Elude the Metropolis Process
• Algorithm 457: finding all cliques of an undirected graph