Near-perfect graphs with polyhedral

DOI10.1016/j.endm.2011.05.067zbMath1268.90031OpenAlexW1576691799MaRDI QIDQ2840742

Silvia M. Bianchi, Tunçel, Levent, Graciela L. Nasini, Mariana S. Escalante

Publication date: 23 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2011.05.067

zbMATH Keywords

integer programmingsemidefinite programmingstable set problemlift-and-project methods

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs ⋮ Characterizing N+-perfect line graphs ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs

Cites Work

• Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Near-perfect matrices
• The stable set problem and the lift-and-project ranks of graphs
• Applying Lehman's theorems to packing problems
• Some advances on Lovász-Schrijver relaxations of the fractional stable set polytope
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph

This page was built for publication: Near-perfect graphs with polyhedral