Persistency of Linear Programming Relaxations for the Stable Set Problem

DOI10.1007/978-3-030-45771-6_27zbMath1503.90080OpenAlexW3023538983MaRDI QIDQ5041757

Stefan Weltge, Elisabeth Rodríguez-Heck, Matthias Walter, Karl Stickler

Publication date: 14 October 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-45771-6_27

zbMATH Keywords

stable setinteger linear programmingpersistency

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• A class of facet producing graphs for vertex packing polyhedra
• On certain polytopes associated with graphs
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Persistency of linear programming relaxations for the stable set problem
• Minimum node covers and 2-bicritical graphs
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Vertex packings: Structural properties and algorithms
• On Linear Characterizations of Combinatorial Optimization Problems
• On the facial structure of set packing polyhedra