The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope

DOI10.1007/978-3-030-63072-0_9MaRDI QIDQ2056893zbMATH OpenOpenAlexFDO

Authors Phillippe Samer, Dag Haugland

Publication date 8 December 2021

Full work available at URL https://hdl.handle.net/11250/2761120

zbMATH Keywords

cardinality constraintscombinatorial optimizationindependent setsinteger programmingstable setsvalid inequalities

Mathematics Subject Classification ID

Applications of graph theory (05C90) Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Fixed cardinality stable sets
• Bounded Stable Sets: Polytopes and Colorings
• Wheel inequalities for stable set polytopes
• The stable set problem: clique and nodal inequalities revisited
• Composition of stable set polyhedra

Cites work

• A branch and cut algorithm for minimum spanning trees under conflict constraints
• A tutorial on branch and cut algorithms for the maximum stable set problem
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• Bounded Stable Sets: Polytopes and Colorings
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficient cuts in Lagrangean `relax-and-cut' schemes
• Finding a Maximum Clique in an Arbitrary Graph
• scientific article; zbMATH DE number 956849 (Why is no real title available?)
• Mathematical programming based heuristics for the 0--1 MIP: a survey
• Non delayed relax-and-cut algorithms
• Paths, trees and matchings under disjunctive constraints
• Properties of vertex packing and independence system polyhedra

Cited in

(3)

• Wheel inequalities for stable set polytopes
• Fixed cardinality stable sets
• An extended formulation for the 1‐wheel inequalities of the stable set polytope

This page was built for publication: The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope

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