Separation routine and extended formulations for the stable set problem in claw-free graphs
type: Item
instance of: scholarly article
title: Separation routine and extended formulations for the stable set problem in claw-free graphs
zbMATH Open document ID: 1470.90051
author: Yuri Faenza
author: Gianpaolo Oriolo
author: Gautier Stauffer
published in: Mathematical Programming. Series A. Series B
publication date: 2021-07-02T00:00:00Z
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7367257
zbMATH Keywords: claw-free graphs
zbMATH Keywords: stable set polytope
zbMATH Keywords: separation algorithm
zbMATH Keywords: extended formulations
MaRDI profile type: Publication
full work available at URL: s10107-020-01502-4
OpenAlex ID: W3022346223
cites work: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
cites work: Minimum Weighted Clique Cover on Strip-Composed Perfect Graphs
cites work: Q3416248
cites work: Claw-free graphs. V. Global structure
cites work: Edmonds polytopes and a hierarchy of combinatorial problems
cites work: Q4371290
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: The stable set polytope of quasi-line graphs
cites work: Q5365068
cites work: Q5743477
cites work: Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
cites work: Exponential lower bounds for polytopes in combinatorial optimization
cites work: Gear composition and the stable set polytope
cites work: The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect
cites work: The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect
cites work: Geometric algorithms and combinatorial optimization
cites work: A cutting plane algorithm for minimum perfect 2-matchings
cites work: Competitive algorithms for multistage online scheduling
cites work: Branched Polyhedral Systems
cites work: Using separation algorithms to generate mixed integer model reformulations
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
cites work: An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
cites work: A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
cites work: Odd Minimum Cut-Sets and b-Matchings
cites work: On facets of stable set polytopes of claw-free graphs with stability number 3
cites work: Q4234148
cites work: The Matching Polytope has Exponential Extension Complexity
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
DOI: 10.1007/S10107-020-01502-4
description: scientific article; zbMATH DE number 7367257