Fixed cardinality stable sets

DOI10.1016/J.DAM.2021.01.019MaRDI QIDQ1983123zbMATH OpenOpenAlexFDO

Authors Phillippe Samer, Dag Haugland

Publication date 15 September 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

cardinality constraintscombinatorial optimizationgraph classesindependent setsinteger programmingstable sets

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope
• Bounded Stable Sets: Polytopes and Colorings
• Recognition of Graphs with Convex Quadratic Stability Number
• Polynomially solvable cases for the maximum stable set problem
• On the number of vertices belonging to all maximum stable sets of a graph

Cites work

• A tutorial on branch and cut algorithms for the maximum stable set problem
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Bounded Stable Sets: Polytopes and Colorings
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Extended formulations for vertex cover
• Finding a Maximum Clique in an Arbitrary Graph
• Graphs and combinatorial optimization: from theory to applications. Proceedings of the 18th Cologne-Twente workshop on graphs and combinatorial optimization (CTW2020), online, September 14--16, 2020
• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 956849 (Why is no real title available?)
• Lagrangean relaxation. (With comments and rejoinder).
• Mathematical programming based heuristics for the 0--1 MIP: a survey
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Non delayed relax-and-cut algorithms
• Parameterized algorithms
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Parameterized extension complexity of independent set and related problems
• Paths, trees and matchings under disjunctive constraints
• Properties of vertex packing and independence system polyhedra
• The matching relaxation for a class of generalized set partitioning problems
• The stable set problem and the thinness of a graph
• Topics in Intersection Graph Theory

Cited in

(6)

• Stable multi-sets
• The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope
• A polyhedral study of the maximum stable set problem with weights on vertex-subsets
• Bounded Stable Sets: Polytopes and Colorings
• Every Stable Set Contains a Fully Stable Set
• Polyhedral results and stronger Lagrangean bounds for stable spanning trees

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Fixed cardinality stable sets

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