Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut

DOI10.1007/S10107-005-0576-5MaRDI QIDQ2583145zbMATH OpenOpenAlexFDO

Authors Pierre Pesneau, Bernard Fortz, A. R. Mahjoub, S. Thomas McCormick

Publication date 13 January 2006

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

Full work available at URL https://doi.org/10.1007/s10107-005-0576-5

zbMATH Keywords

branch-and-cut algorithmnetwork design problem

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Polyhedral results for two-connected networks with bounded rings
• scientific article; zbMATH DE number 1187146
• Two-edge connected spanning subgraphs and polyhedra
• On two-connected subgraph polytopes
• On the two-connected planar spanning subgraph polytope
• On the Steiner 2-edge connected subgraph polytope
• Polyhedra of the Equivalent Subgraph Problem and Some Edge Connectivity Problems
• On 2-connected spanning subgraphs with bounded degree in \(K _{1,r }\)-free graphs
• The k-node connected subgraph problem: polyhedral analysis and branch-and-cut
• scientific article; zbMATH DE number 3916310

Cites work

• k-edge connected polyhedra on series-parallel graphs
• A new approach to the maximum-flow problem
• Design of Survivable Networks: A survey
• scientific article; zbMATH DE number 1535630 (Why is no real title available?)
• scientific article; zbMATH DE number 742961 (Why is no real title available?)
• scientific article; zbMATH DE number 795223 (Why is no real title available?)
• Multi-Terminal Network Flows
• On two-connected subgraph polytopes
• Optimal attack and reinforcement of a network
• Polyhedral results for two-connected networks with bounded rings
• Separating from the dominant of the spanning tree polytope
• Separation of partition inequalities
• Solving the Two-Connected Network with Bounded Meshes Problem
• The k-Edge-Connected Spanning Subgraph Polyhedron
• The complexity of finding maximum disjoint paths with length constraints
• Two-connected networks with rings of bounded cardinality
• Two-edge connected spanning subgraphs and polyhedra
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• Very Simple Methods for All Pairs Network Flow Analysis

Cited in

(20)

• Two-connected networks with rings of bounded cardinality
• On imposing connectivity constraints in integer programs
• Stochastic survivable network design problems: theory and practice
• On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
• Polyhedral results for two-connected networks with bounded rings
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• Critical extreme points of the 2-edge connected spanning subgraph polytope
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Survivability in hierarchical telecommunications networks
• A branch-and-cut algorithm for the k-edge connected subgraph problem
• Hierarchical survivable network design problems
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• A branch-and-cut algorithm for two-level survivable network design problems
• The k edge-disjoint 3-hop-constrained paths polytope
• A decomposition algorithm for the ring spur assignment problem
• The edge-labeled survivable network design problem: formulations and branch-and-cut
• A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints
• Network design with vulnerability constraints and probabilistic edge reliability
• Rapid prototyping of optimization algorithms using COIN-OR: a case study involving the cutting-stock problem

Describes a project that uses

Uses Software

• SYMPHONY

This page was built for publication: Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut

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