On the facets of the lift-and-project relaxations of graph subdivisions

DOI10.1016/J.ENDM.2011.05.035MaRDI QIDQ2840709zbMATH OpenOpenAlexFDO

Authors Néstor E. Aguilera, Pablo G. Fekete, 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.035

zbMATH Keywords

stable set problemgraph subdivisionlift-and-project

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• On the facets of lift-and-project relaxations under graph operations
• Lift and project relaxations for the matching and related polytopes
• Lift-and-project cuts and perfect graphs
• On the linear relaxation of the 2-node connected subgraph polytope
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
• On the complexity of partitioning graphs into connected subgraphs
• Complexity of subdivision-vertex and subdivision-edge join graphs
• \(L(2,1)\)-labelings of subdivisions of graphs

Cites work

• Compositions of Graphs and Polyhedra II: Stable Sets
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Critical facets of the stable set polytope
• Further facet generating procedures for vertex packing polytopes
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• On the stable set polytope of a series-parallel graph
• The stable set problem and the lift-and-project ranks of graphs

Cited in

(3)

• scientific article; zbMATH DE number 6707767 (Why is no real title available?)
• On the facets of lift-and-project relaxations under graph operations
• The stable set problem and the lift-and-project ranks of graphs

This page was built for publication: On the facets of the lift-and-project relaxations of graph subdivisions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840709)