Stable Set Polytopes for a Class of Circulant Graphs

DOI10.1137/S1052623497321973MaRDI QIDQ4702296zbMATH OpenFDO

Authors Geir Dahl

Publication date 24 November 1999

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S1052623497321973

zbMATH Keywords

circulant graphspolyhedral combinatoricsstable sets

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) (n)-dimensional polytopes (52B11) Combinatorial optimization (90C27)

Recommendations

• On the facets of stable set polytopes of circular interval graphs
• The stable set polytope and some operations on graphs
• On cycles and the stable multi-set polytope
• The stable set polytope of icosahedral graphs
• The stable set polytope of quasi-line graphs
• Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs
• On the stable set polytope of a series-parallel graph
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
• On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs

Cited in

(21)

• The 2-hop spanning tree problem
• Wheel inequalities for stable set polytopes
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Polyhedral results on the stable set problem in graphs containing even or odd pairs
• Stability critical graphs and ranks facets of the stable set polytope
• A new lifting theorem for vertex packing
• On non-rank facets of stable set polytopes of webs with clique number four
• Almost all webs are not rank-perfect
• Stable set polytopes in a higher dimensional space
• Strength of facets for the set covering and set packing polyhedra on circulant matrices
• Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs
• A friction factor bound for transitional pipe flow
• On claw-free t-perfect graphs
• On the b-Stable Set Polytope of Graphs without Bad K₄
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• Sink-Stable Sets of Digraphs
• scientific article; zbMATH DE number 2230253 (Why is no real title available?)
• A note on certain subpolytopes of the assignment polytope associated with circulant graphs
• A construction for non-rank facets of stable set polytopes of webs
• The stable set polytope of icosahedral graphs
• The stable set polytope of quasi-line graphs

This page was built for publication: Stable Set Polytopes for a Class of Circulant Graphs

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