On the facets of lift-and-project relaxations under graph operations

DOI10.1016/j.dam.2012.07.012zbMath1288.05211OpenAlexW2086105421MaRDI QIDQ2448871

Pablo G. Fekete, Néstor E. Aguilera, Mariana S. Escalante

Publication date: 5 May 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.07.012

zbMATH Keywords

stable setlift-and-project operatorsoperations in graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Integer programming (90C10) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

Cites Work

• Critical facets of the stable set polytope
• 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
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A New Facet Generating Procedure for the Stable Set Polytope
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Further facet generating procedures for vertex packing polytopes
• Facet Obtaining Procedures for Set Packing Problems
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra