An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
From MaRDI portal
Publication:2390997
DOI10.1007/s10107-008-0219-8zbMath1176.90494OpenAlexW2139740075WikidataQ57702237 ScholiaQ57702237MaRDI QIDQ2390997
Adam N. Letchford, Stefano Smriglio, Monia Giandomenico, Fabrizio Rossi
Publication date: 24 July 2009
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-008-0219-8
Related Items
The stable set problem: clique and nodal inequalities revisited, Strong lift-and-project cutting planes for the stable set problem, Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms, An extended formulation for the 1‐wheel inequalities of the stable set polytope, The Steiner connectivity problem, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, On the Lovász theta function and some variants, A new lift-and-project operator, Strengthening Chvátal-Gomory Cuts for the Stable Set Problem, The Chvátal closure of generalized stable sets in bidirected graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
- A boundary point method to solve semidefinite programs
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- Matrices with the Edmonds-Johnson property
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Geometric algorithms and combinatorial optimization
- A class of facet producing graphs for vertex packing polyhedra
- Connection between semidefinite relaxations of the max-cut and stable set problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Antiweb-wheel inequalities and their separation problems over the stable set polytopes
- Exploring the relationship between max-cut and stable set relaxations
- On extracting maximum stable sets in perfect graphs using Lovász's theta function
- Anti-blocking polyhedra
- Normal hypergraphs and the perfect graph conjecture
- A comparison of the Delsarte and Lovász bounds
- Cones of Matrices and Set-Functions and 0–1 Optimization
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- On the Shannon capacity of a graph
- Solving Airline Crew Scheduling Problems by Branch-and-Cut
- Computational Experience with Stable Set Relaxations
- On the facial structure of set packing polyhedra
- Regularization Methods for Semidefinite Programming
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- Principles and Practice of Constraint Programming – CP 2003
- A branch-and-cut algorithm for the maximum cardinality stable set problem
