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

DOI10.1016/j.orl.2005.10.008zbMath1109.05098WikidataQ123344904 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 set; graph subdivision; lift-and-project

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope, Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, Lovász-Schrijver PSD-Operator on Claw-Free Graphs, Near-perfect graphs with polyhedral, Characterizing N+-perfect line graphs, Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• 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