Fixed cardinality stable sets

DOI10.1016/j.dam.2021.01.019zbMath1477.90091OpenAlexW3127315540MaRDI QIDQ1983123

Phillippe Samer, Dag Haugland

Publication date: 15 September 2021

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

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

zbMATH Keywords

integer programmingcombinatorial optimizationindependent setscardinality constraintsstable setsgraph classes

Mathematics Subject Classification ID

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

Related Items (1)

Polyhedral results and stronger Lagrangean bounds for stable spanning trees

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Paths, trees and matchings under disjunctive constraints
• Non delayed relax-and-cut algorithms
• The matching relaxation for a class of generalized set partitioning problems
• Extended formulations for vertex cover
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Lagrangean relaxation. (With comments and rejoinder).
• Mathematical programming based heuristics for the 0--1 MIP: a survey
• Parameterized extension complexity of independent set and related problems
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• The stable set problem and the thinness of a graph
• Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Finding a Maximum Clique in an Arbitrary Graph
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Topics in Intersection Graph Theory
• Bounded Stable Sets: Polytopes and Colorings
• Properties of vertex packing and independence system polyhedra
• A tutorial on branch and cut algorithms for the maximum stable set problem
• Graphs and Combinatorial Optimization: from Theory to Applications
• No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
• Parameterized Algorithms

This page was built for publication: Fixed cardinality stable sets