On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem

DOI10.1016/j.cor.2017.02.017zbMath1391.90607OpenAlexW2589796617MaRDI QIDQ1652309

Hua Jiang, Chu-Min Li, Felip Manyà

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2017.02.017

zbMATH Keywords

branch-and-boundmaximum clique problembranching orderingincremental maxsat reasoning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The maximum clique problem for permutation Hamming graphs ⋮ An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ The maximum clique interdiction problem ⋮ A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs ⋮ A new upper bound for the maximum weight clique problem ⋮ A new branch-and-bound algorithm for the maximum weighted clique problem ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ A new branch-and-filter exact algorithm for binary constraint satisfaction problems ⋮ A maximum edge-weight clique extraction algorithm based on branch-and-bound

Uses Software

• MaxCliqueDyn
• BBMCL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Breakout local search for maximum clique problems
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• An exact bit-parallel algorithm for the maximum clique 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
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• A fast algorithm for the maximum clique problem
• Exact algorithms for maximum clique: a computational study
• Multi-threading a state-of-the-art maximum clique algorithm
• Relaxed approximate coloring in exact maximum clique search
• Mining market data: a network approach
• A review on algorithms for maximum clique problems
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Keller’s cube-tiling conjecture is false in high dimensions
• Greedy and heuristic algorithms for codes and colorings
• A tutorial on branch and cut algorithms for the maximum stable set problem
• Optimal Protein Structure Alignment Using Maximum Cliques
• Principles and Practice of Constraint Programming – CP 2003
• A branch and bound algorithm for the maximum clique problem