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

DOI10.1007/s10898-013-0075-9zbMath1294.05124OpenAlexW2013020979MaRDI QIDQ2249809

Mikhail Batsyn, Panos M. Pardalos, Evgeny Maslov

Publication date: 3 July 2014

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

Full work available at URL: https://doi.org/10.1007/s10898-013-0075-9

zbMATH Keywords

graph colouringbranch and bound algorithmmaximum clique problemheuristic solution

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Ulam stability of a functional equation deriving from quadratic and additive mappings in random normed spaces, A review on algorithms for maximum clique problems, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, The stable set problem: clique and nodal inequalities revisited, CliSAT: a new exact algorithm for hard maximum clique problems, Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications, A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, Dynamic node packing

Uses Software

• MaxCliqueDyn
• Tabu search
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Reducibility among Combinatorial Problems
• Algorithm 457: finding all cliques of an undirected graph
• Sur le coloriage des graphs