On extracting maximum stable sets in perfect graphs using Lovász's theta function
From MaRDI portal
Publication:2506178
DOI10.1007/s10589-005-3060-5zbMath1103.90075MaRDI QIDQ2506178
E. Alper Yıldırım, Xiaofei Fan-Orzechowski
Publication date: 28 September 2006
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/11693/23840
90C22: Semidefinite programming
Related Items
A heuristic for the stability number of a graph based on convex quadratic programming and tabu search, A simpler characterization of a spectral lower bound on the clique number, An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving semidefinite-quadratic-linear programs using SDPT3
- The strong perfect graph theorem
- Geometric algorithms and combinatorial optimization
- The sandwich theorem
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Approximating the independence number via the \(\vartheta\)-function
- Maximum stable set formulations and heuristics based on continuous optimization
- Solving problems with semidefinite and related constraints using interior-point methods for nonlinear programming
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Solving a class of semidefinite programs via nonlinear programming
- Recognizing Berge graphs
- On a Representation of the Matching Polytope Via Semidefinite Liftings
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- Computational Experience with Stable Set Relaxations
- A Spectral Bundle Method for Semidefinite Programming
- Sur le coloriage des graphs