Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture

DOI10.1016/j.orl.2005.10.008zbMath1109.05098OpenAlexW1533248588WikidataQ123344904 ScholiaQ123344904MaRDI QIDQ867926

Mariana S. Escalante, Graciela L. Nasini, M. Susana Montelar

Publication date: 19 February 2007

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2005.10.008

zbMATH Keywords

stable setgraph subdivisionlift-and-project

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

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 ⋮ Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs ⋮ Near-perfect graphs with polyhedral

Cites Work

• The sandwich theorem
• On certain polytopes associated with graphs
• The stable set problem and the lift-and-project ranks of graphs
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture