The stable set problem and the lift-and-project ranks of graphs
From MaRDI portal
Publication:1424302
DOI10.1007/s10107-003-0407-5zbMath1160.90584MaRDI QIDQ1424302
Publication date: 11 March 2004
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-003-0407-5
Integer programming; Semidefinite programming; Lift-and-project; Semidefinite lifting; Stable set problem
90C22: Semidefinite programming
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27: Combinatorial optimization
90C09: Boolean programming
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Unnamed Item, Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs, Handelman's hierarchy for the maximum stable set problem, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, On the behavior of the \(N_{+}\)-operator under blocker duality, Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture, On the polyhedral lift-and-project methods and the fractional stable set polytope, Lift-and-project ranks of the set covering polytope of circulant matrices, Strong reductions for extended formulations, Lift-and-project ranks and antiblocker duality, On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets, Tree-width and the Sherali-Adams operator, On the facets of lift-and-project relaxations under graph operations, Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope, Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra, On the commutativity of antiblocker diagrams under lift-and-project operators, Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Lovász-Schrijver PSD-Operator on Claw-Free Graphs, On the facets of the lift-and-project relaxations of graph subdivisions, Near-perfect graphs with polyhedral, Characterizing N+-perfect line graphs, Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes, Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs
