The stable set problem: clique and nodal inequalities revisited
From MaRDI portal
Publication:2664356
DOI10.1016/j.cor.2020.105024zbMath1458.90550OpenAlexW3035984753MaRDI QIDQ2664356
Adam N. Letchford, Stefano Smriglio, Fabrizio Rossi
Publication date: 20 April 2021
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/144569/1/nodal.pdf
Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
An SDP-based approach for computing the stability number of a graph, Boosting ant colony optimization via solution prediction and machine learning, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, Worst-case analysis of clique MIPs
Uses Software
Cites Work
- Strong lift-and-project cutting planes for the stable set problem
- A branch and cut solver for the maximum stable set problem
- An exact bit-parallel algorithm for the maximum clique problem
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- An exact algorithm for the maximum clique problem
- Geometric algorithms and combinatorial optimization
- Facets for node packing
- The maximum clique problem
- A multi-KP modeling for the maximum-clique problem
- Wheel inequalities for stable set polytopes
- On certain polytopes associated with graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Antiweb-wheel inequalities and their separation problems over the stable set polytopes
- A fast algorithm for the maximum clique problem
- Exact algorithms for maximum clique: a computational study
- General cut-generating procedures for the stable set polytope
- Speeding up branch and bound algorithms for solving the maximum clique problem
- An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
- A new trust region technique for the maximum weight clique problem
- Exploring the relationship between max-cut and stable set relaxations
- A review on algorithms for maximum clique problems
- Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms
- Cones of Matrices and Set-Functions and 0–1 Optimization
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- Computational Experience with Stable Set Relaxations
- Properties of vertex packing and independence system polyhedra
- On the facial structure of set packing polyhedra
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- The chromatic number of random graphs
- New facets for the set packing polytope
- A branch-and-cut algorithm for the maximum cardinality stable set problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
