A branch-and-cut algorithm for the k-edge connected subgraph problem

DOI10.1002/NET.20310zbMATH Open1207.05192OpenAlexW4236709137MaRDI QIDQ3057129FDOQ3057129

Authors:

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20310

Recommendations

• The \(k\)-node connected subgraph problem: polyhedral analysis and branch-and-cut
• The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points.
• scientific article; zbMATH DE number 764407
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut

zbMATH Keywords

polytopebranch-and-cutfacetseparationreduction operations\(k\)-edge connected graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• The traveling salesman problem on a graph and some related integer polyhedra
• Design of Survivable Networks: A survey
• A new approach to the maximum-flow problem
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• Multi-Terminal Network Flows
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points.
• \(k\)-edge connected polyhedra on series-parallel graphs
• Title not available (Why is that?)
• The k-Edge-Connected Spanning Subgraph Polyhedron
• Two-edge connected spanning subgraphs and polyhedra
• Very Simple Methods for All Pairs Network Flow Analysis
• Steiner 2-Edge Connected Subgraph Polytopes on Series-Parallel Graphs
• On two-connected subgraph polytopes
• Steiner \(k\)-edge connected subgraph polyhedra
• Critical extreme points of the 2-edge connected spanning subgraph polytope
• Title not available (Why is that?)
• Quantum abacus
• On the Structure of Minimum-Weight k-Connected Spanning Networks
• Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs
• The traveling salesman problem in graphs with some excluded minors
• Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements
• On perfectly two-edge connected graphs
• The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs
• On the 3-Terminal Cut Polyhedron
• An Integer Polytope Related to the Design of Survivable Communication Networks

Cited In (16)

• A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints
• On the \(k\)-edge-incident subgraph problem and its variants
• Survivability in hierarchical telecommunications networks
• The \(k\) edge-disjoint 3-hop-constrained paths polytope
• Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
• \(k\)-edge subgraph problems
• Network design with vulnerability constraints and probabilistic edge reliability
• Probabilistic properties of highly connected random geometric graphs
• The k-Edge-Connected Spanning Subgraph Polyhedron
• The \(k\)-node connected subgraph problem: polyhedral analysis and branch-and-cut
• On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
• A branch \& cut algorithm for the maximum common edge subgraph problem
• Design of survivable networks with low connectivity requirements
• The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points.
• Box-total dual integrality and edge-connectivity
• Title not available (Why is that?)

Uses Software

• ABACUS
• CPLEX

This page was built for publication: A branch-and-cut algorithm for the \(k\)-edge connected subgraph problem

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