On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
From MaRDI portal
Publication:1652309
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
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
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
