Improvements to MCS algorithm for the maximum clique problem

DOI10.1007/s10878-012-9592-6zbMath1290.90063OpenAlexW2096592688MaRDI QIDQ2444144

Panos M. Pardalos, Mikhail Batsyn, Evgeny Maslov, Boris I. Goldengorin

Publication date: 8 April 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9592-6

zbMATH Keywords

branch-and-bound algorithmgraph colouringmaximum clique problemheuristic solution

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (13)

A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations ⋮ Infra-chromatic bound for exact maximum clique search ⋮ Finding near-optimal independent sets at scale ⋮ An exact algorithm for the maximum probabilistic clique problem ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique ⋮ Multi-threading a state-of-the-art maximum clique algorithm ⋮ A nonconvex quadratic optimization approach to the maximum edge weight clique problem ⋮ Relaxed approximate coloring in exact maximum clique search ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ A clique search problem and its application to machine scheduling

Uses Software

• DIMACS
• Tabu search
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A neural algorithm for the maximum clique problem: Analysis, experiments, and circuit implementation
• Greedy randomized adaptive search procedures
• A hybrid heuristic for the maximum clique problem
• Clique-detection models in computational biochemistry and genomics
• A new table of constant weight codes
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Finding a Maximum Clique in an Arbitrary Graph
• Large Cliques Elude the Metropolis Process
• Handbook of Combinatorial Optimization
• Algorithm 457: finding all cliques of an undirected graph
• Sur le coloriage des graphs

This page was built for publication: Improvements to MCS algorithm for the maximum clique problem