The k-Edge-Connected Spanning Subgraph Polyhedron

DOI10.1137/S0895480191222665MaRDI QIDQ4296519zbMATH OpenOpenAlexFDO

Authors 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

\(k\)-edge-connected spanning subgraphsconvex hullfacetfacet-defining inequalitiesouter planar graphpolyhedron

Mathematics Subject Classification ID

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

Recommendations

• The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points.
• On \(k\)-edge-connected polyhedra: box-TDIness in series-parallel graphs
• A branch-and-cut algorithm for the k-edge connected subgraph problem
• The 2-edge-connected subgraph polyhedron
• On two-connected subgraph polytopes

Cited in

(21)

• On perfectly two-edge connected graphs
• 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 two-connected subgraph polytopes
• On \(k\)-edge-connected polyhedra: box-TDIness in series-parallel graphs
• 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
• Box-total dual integrality and edge-connectivity
• Minimum cost k edges connected subgraph problems
• A branch-and-cut algorithm for the k-edge connected subgraph problem
• The k-node connected subgraph problem: polyhedral analysis and branch-and-cut
• Edges and Kuratowski Subgraphs of Non-Planar Graphs
• On the Steiner 2-edge connected subgraph polytope
• Polyhedra of the Equivalent Subgraph Problem and Some Edge Connectivity Problems
• The k edge-disjoint 3-hop-constrained paths polytope
• On the dominant of the Steiner 2-edge connected subgraph polytope
• Design of survivable networks with low connectivity requirements
• Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron

This page was built for publication: The k-Edge-Connected Spanning Subgraph Polyhedron

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