On the facets of stable set polytopes of circular interval graphs

DOI10.1007/S10479-021-04449-7MaRDI QIDQ2673814zbMATH OpenOpenAlexFDO

Authors Gianpaolo Oriolo, Gautier Stauffer

Publication date 13 June 2022

Published in Annals of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10479-021-04449-7

zbMATH Keywords

circular interval graphsfacetspolyhedral descriptionsquasi-line graphsstable sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph operations (line graphs, products, etc.) (05C76) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• The stable set polytope of quasi-line graphs
• On the facets of the stable set polytope of quasi-line graphs
• Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Generalized clique family inequalities for claw-free graphs

Cites work

• A class of facet producing graphs for vertex packing polyhedra
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Almost all webs are not rank-perfect
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Clique-circulants and the stable set polytope of fuzzy circular interval graphs
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3496213 (Why is no real title available?)
• scientific article; zbMATH DE number 2196279 (Why is no real title available?)
• Lifting the facets of zero–one polytopes
• Matching theory
• Maximum matching and a polyhedron with 0,1-vertices
• Minmax relations for cyclically ordered digraphs
• On dominating set polyhedra of circular interval graphs
• On maximal independent sets of vertices in claw-free graphs
• On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs
• On stable set polyhedra for K//(1,3)free graphs
• On the facets of the stable set polytope of quasi-line graphs
• On the facial structure of set packing polyhedra
• Solving the weighted stable set problem in claw-free graphs via decomposition
• Stable sets in claw-free graphs: a journey through algorithms and polytopes
• The rank facets of the stable set polytope for claw-free graphs
• The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect
• The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect
• The stable set polytope of quasi-line graphs

Cited in

(9)

• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Stability critical graphs and ranks facets of the stable set polytope
• On dominating set polyhedra of circular interval graphs
• Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs
• Stable Set Polytopes for a Class of Circulant Graphs
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• On the facets of the stable set polytope of quasi-line graphs
• The stable set polytope of icosahedral graphs
• Clique-circulants and the stable set polytope of fuzzy circular interval graphs

This page was built for publication: On the facets of stable set polytopes of circular interval graphs

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