On extracting maximum stable sets in perfect graphs using Lovász's theta function

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

zbMATH Keywords

semidefinite programming; perfect graphs; Lovász's theta function; maximum stable sets

Mathematics Subject Classification ID

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

• SDPT3
• Max-AO

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