Speeding up MCS algorithm for the maximum clique problem with ILS heuristic and other enhancements

DOI10.1007/978-1-4614-8588-9_7MaRDI QIDQ2820111zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Improvements to MCS algorithm for the maximum clique problem
• Speeding up branch and bound algorithms for solving the maximum clique problem
• A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• Exact algorithms for maximum clique: a computational study

Cites work

• scientific article; zbMATH DE number 4064507 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• A hybrid heuristic for the maximum clique problem
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• Algorithm 457: finding all cliques of an undirected graph
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• Fast local search for the maximum independent set problem
• Greedy randomized adaptive search procedures
• Large Cliques Elude the Metropolis Process
• Simple ingredients leading to very efficient heuristics for the maximum clique problem

Cited in

(3)

• On comparing algorithms for the maximum clique problem
• Speeding up branch and bound algorithms for solving the maximum clique problem
• Improvements to MCS algorithm for the maximum clique problem

Describes a project that uses

Uses Software

• Tabu search

This page was built for publication: Speeding up MCS algorithm for the maximum clique problem with ILS heuristic and other enhancements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2820111)