\(k\)-edge connected polyhedra on series-parallel graphs

DOI10.1016/0167-6377(96)00015-6zbMath0865.90049OpenAlexW2091402313MaRDI QIDQ2564304

Yanyan Li

Publication date: 6 July 1997

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(96)00015-6

zbMATH Keywords

series-parallel graphs\(k\)-edge connected spanning subgraph polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18)

Related Items (14)

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 ⋮ 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. ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ Circuit and bond polytopes on series-parallel graphs ⋮ 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 ⋮ Critical extreme points of the 2-edge connected spanning subgraph polytope ⋮ Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The traveling salesman problem in graphs with some excluded minors
• Separating from the dominant of the spanning tree polytope
• The Steiner tree polytope and related polyhedra
• Tree polytope on 2-trees
• Two-edge connected spanning subgraphs and polyhedra
• On two-connected subgraph polytopes
• 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
• On the Structure of Minimum-Weight k-Connected Spanning Networks
• The traveling salesman problem on a graph and some related integer polyhedra
• Optimal attack and reinforcement of a network
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints
• The k-Edge-Connected Spanning Subgraph Polyhedron
• Matroids and the greedy algorithm

This page was built for publication: \(k\)-edge connected polyhedra on series-parallel graphs