Strengthening Chvátal-Gomory cuts for the stable set problem
From MaRDI portal
Publication:2835677
DOI10.1007/978-3-319-45587-7_18zbMATH Open1452.90272OpenAlexW2416465474MaRDI QIDQ2835677FDOQ2835677
Authors: Adam N. Letchford, Francesca Marzi, Fabrizio Rossi, Stefano Smriglio 
Publication date: 30 November 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/79029/7/isco_stable_set.pdf
Recommendations
- Strong lift-and-project cutting planes for the stable set problem
- A strengthened general cut-generating procedure for the stable set polytope
- Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
- Computational Experience with Stable Set Relaxations
- A new approach to the stable set problem based on ellipsoids
Cites Work
- Geometric algorithms and combinatorial optimization
- On the Shannon capacity of a graph
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Outline of an algorithm for integer solutions to linear programs
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the facial structure of set packing polyhedra
- Copositivity cuts for improving SDP bounds on the clique number
- Optimizing over the first Chvátal closure
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- A branch-and-cut algorithm for the maximum cardinality stable set problem
- A branch and cut solver for the maximum stable set problem
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Edmonds polytopes and a hierarchy of combinatorial problems
- A strengthened general cut-generating procedure for the stable set polytope
- Strong lift-and-project cutting planes for the stable set problem
- An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- Computational Experience with Stable Set Relaxations
- Title not available (Why is that?)
- The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
- Coefficient strengthening: a tool for reformulating mixed-integer programs
- Ellipsoidal relaxations of the stable set problem: theory and algorithms
- Improving upper bounds for the clique number by non-valid inequalities
- On the separation of topology-free rank inequalities for the max stable set problem
- On the Chvàtal rank of linear relaxations of the stable set polytope
Cited In (9)
- A new approach to the stable set problem based on ellipsoids
- Strengthening Gomory Mixed-Integer Cuts
- Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
- Ellipsoidal relaxations of the stable set problem: theory and algorithms
- Strong bounds for resource constrained project scheduling: preprocessing and cutting planes
- A strengthened general cut-generating procedure for the stable set polytope
- Stable sets, corner polyhedra and the Chvàtal closure
- Strong lift-and-project cutting planes for the stable set problem
- Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
Uses Software
This page was built for publication: Strengthening Chvátal-Gomory cuts for the stable set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835677)
