Compositions of Graphs and Polyhedra II: Stable Sets

DOI10.1137/S0895480190182678MaRDI QIDQ4307045zbMATH OpenOpenAlexFDO

Authors Francisco Barahona, A. R. Mahjoub

Publication date 24 October 1994

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

compact systemcomposition of polyhedrainequalitiesminorpolyhedral combinatoricsseries-parallel graphsstable setstable set polytopestable set problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• Composition of stable set polyhedra
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor

Cited in

(37)

• Gear composition and the stable set polytope
• On the stable set polytope of a series-parallel graph
• Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
• Compositions in the bipartite subgraph polytope
• Stable sets and polynomials
• Stable set bonding in perfect graphs and parity graphs
• One-node cutsets and the dominating set polytope
• Fractional and integral colourings
• The stable set polytope and some operations on graphs
• On decomposability of multilinear sets
• Polyhedral results on the stable set problem in graphs containing even or odd pairs
• Extended formulations for vertex cover
• Composition of graphs and the triangle-free subgraph polytope
• Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
• A new lifting theorem for vertex packing
• On the complete set packing and set partitioning polytopes: properties and rank 1 facets
• 2-clique-bond of stable set polyhedra
• The wheels of the orthogonal Latin squares polytope: classification and valid inequalities
• New facets for the two-stage uncapacitated facility location polytope
• Claw-free t-perfect graphs can be recognized in polynomial time
• Composition of graphs and the triangle free subgraph polytope
• A new facet generating procedure for the stable set polytope
• On the facets of the lift-and-project relaxations of graph subdivisions
• Characterising claw-free t-perfect graphs
• The stable set polytope of claw-free graphs with large stability number
• Gear composition of stable set polytopes and G-perfection
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
• On claw-free t-perfect graphs
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• Separation problems for the stable set polytope
• New facets for the set packing polytope
• Stable 2-pairs and (X,Y)-intersection graphs
• A branch-and-cut algorithm for the maximum cardinality stable set problem
• Stable sets and graphs with no even holes
• The stable set polytope of icosahedral graphs
• Composition of stable set polyhedra

This page was built for publication: Compositions of Graphs and Polyhedra II: Stable Sets

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