The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs

DOI10.1016/0166-218X(94)00135-ZzbMath0846.90116OpenAlexW2103384600MaRDI QIDQ1917298

Ronald L. Rardin, Abdur Rais, Donald K. Wagner, Collette R. Coullard

Publication date: 30 September 1996

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00135-z

zbMATH Keywords

2-connected Steiner subgraphslinear-inequality descriptiontraveling-salesman polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Related Items

On perfectly two-edge connected graphs, On two-connected subgraph polytopes, The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs, The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points., On survivable network polyhedra, On the dominant of the Steiner 2-edge connected subgraph polytope, On the Steiner 2-edge connected subgraph polytope, A branch-and-cut algorithm for the k-edge connected subgraph problem, \(k\)-edge connected polyhedra on series-parallel graphs, Critical extreme points of the 2-edge connected spanning subgraph polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum-weight two-connected spanning networks
• The extremal length of a network
• Two-edge connected spanning subgraphs and polyhedra
• Four problems on graphs with excluded minors
• The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs
• Topology of series-parallel networks
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• Generalized steiner problem in series-parallel networks
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
• Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs