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

DOI10.1016/J.DAM.2012.07.012zbMATH Open1288.05211OpenAlexW2086105421MaRDI QIDQ2448871FDOQ2448871

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

Recommendations

• On the facets of the lift-and-project relaxations of graph subdivisions
• The stable set problem and the lift-and-project ranks of graphs
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• Lift-and-project cuts and perfect graphs
• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure

zbMATH Keywords

stable setlift-and-project operatorsoperations in graphs

Mathematics Subject Classification ID

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

Cites Work

• Properties of vertex packing and independence system polyhedra
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the facial structure of set packing polyhedra
• The stable set problem and the lift-and-project ranks of graphs
• A new facet generating procedure for the stable set polytope
• Facet Obtaining Procedures for Set Packing Problems
• On the stable set polytope of a series-parallel graph
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• Further facet generating procedures for vertex packing polytopes
• Critical facets of the stable set polytope

Cited In (6)

• On the polyhedral lift-and-project methods and the fractional stable set polytope
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• The stable set problem and the lift-and-project ranks of graphs
• Title not available (Why is that?)
• On the facets of the lift-and-project relaxations of graph subdivisions
• A comparison between lift-and-project indices and imperfection ratio on web graphs

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

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