Two-edge connected spanning subgraphs and polyhedra

DOI10.1007/BF01582572zbMath0820.90117MaRDI QIDQ1330901

Ali Ridha Mahjoub

Publication date: 10 August 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

polyhedratraveling salesmanfacetsseries-parallel graphsdesign of reliable communication and transportation networkstwo-edge connected spanning subgraph of minimum weight

Mathematics Subject Classification ID

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

Related Items (29)

Minimum Cost ≤k Edges Connected Subgraph Problems ⋮ Arborescence polytopes for series-parallel graphs ⋮ Two-edge connected spanning subgraphs and polyhedra ⋮ Survivability in hierarchical telecommunications networks ⋮ Separation of partition inequalities with terminals ⋮ On perfectly two-edge connected graphs ⋮ A branch-and-cut algorithm for two-level survivable network design problems ⋮ Optimization in telecommunication networks ⋮ Design of survivable IP-over-optical networks ⋮ On two-connected subgraph polytopes ⋮ The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs ⋮ Spanning cactus: complexity and extensions ⋮ Box-total dual integrality and edge-connectivity ⋮ Survivability in Hierarchical Telecommunications Networks Under Dual Homing ⋮ Facet Generating Techniques ⋮ 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 ⋮ The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation ⋮ The box-TDI system associated with 2-edge connected spanning subgraphs ⋮ Generalized network design problems. ⋮ \(k\)-edge connected polyhedra on series-parallel graphs ⋮ A Network Design Problem with Two-Edge Matching Failures ⋮ 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 ⋮ The Steiner tree polytope and related polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum-weight two-connected spanning networks
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• The traveling salesman problem in graphs with some excluded minors
• Two-edge connected spanning subgraphs and polyhedra
• On two-connected subgraph polytopes
• Topology of series-parallel networks
• A Cutting Plane Algorithm for the Linear Ordering Problem
• Maximal Flow Through a Network
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• The traveling salesman problem: An update of research
• The traveling salesman problem on a graph and some related integer polyhedra
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

This page was built for publication: Two-edge connected spanning subgraphs and polyhedra