Incremental Upper Bound for the Maximum Clique Problem

DOI10.1287/IJOC.2017.0770OpenAlexW2776934400MaRDI QIDQ5131716

Chu-Min Li, Hua Jiang, Zhiwen Fang, Ke Xu

Publication date: 9 November 2020

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2017.0770

zbMATH Keywords

MaxSATmaxcliqueincremental upper bound

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorics (05-XX)

Related Items (10)

An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network ⋮ Research trends in combinatorial optimization ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ A new branch-and-bound algorithm for the maximum weighted clique problem ⋮ Computing lower bounds for minimum sum coloring and optimum cost chromatic partition ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ A branch-and-cut algorithm for the edge interdiction clique problem ⋮ Learning driven three-phase search for the maximum independent union of cliques problem ⋮ A new branch-and-filter exact algorithm for binary constraint satisfaction problems

Uses Software

• MaxCliqueDyn

Cites Work

• Unnamed Item
• 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
• Optimizing with minimum satisfiability
• A review on algorithms for maximum clique problems
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Optimal Protein Structure Alignment Using Maximum Cliques
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: Incremental Upper Bound for the Maximum Clique Problem