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

DOI10.1007/s10898-013-0075-9zbMath1294.05124MaRDI 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 colouring; branch and bound algorithm; maximum clique problem; heuristic solution

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

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

Uses Software

• MaxCliqueDyn
• Tabu search
• Algorithm 457

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item