The k-Edge-Connected Spanning Subgraph Polyhedron

DOI10.1137/S0895480191222665zbMath0821.90123OpenAlexW2046469316MaRDI QIDQ4296519

Sunil Chopra

Publication date: 19 June 1994

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

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

zbMATH Keywords

facet-defining inequalitiespolyhedronconvex hullfacetouter planar graph\(k\)-edge-connected spanning subgraphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Connectivity (05C40)

Related Items

Minimum Cost ≤k Edges Connected Subgraph Problems ⋮ Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron ⋮ The \(k\)-node connected subgraph problem: polyhedral analysis and branch-and-cut ⋮ On perfectly two-edge connected graphs ⋮ On two-connected subgraph polytopes ⋮ Box-total dual integrality and edge-connectivity ⋮ The \(k\) edge-disjoint 3-hop-constrained paths polytope ⋮ The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points. ⋮ Stochastic survivable network design problems: theory and practice ⋮ 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 ⋮ The 2-edge-connected subgraph polyhedron ⋮ Critical extreme points of the 2-edge connected spanning subgraph polytope ⋮ Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut