On survivable network polyhedra

DOI10.1016/j.disc.2004.08.017zbMath1079.90022OpenAlexW1965140003MaRDI QIDQ1772416

Hervé L. M. Kerivin, Ali Ridha Mahjoub

Publication date: 18 April 2005

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2004.08.017

zbMATH Keywords

Polynomial algorithmPolyhedronCutSeries-parallel graphSurvivable network

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Survivability in hierarchical telecommunications networks, A branch-and-cut algorithm for two-level survivable network design problems, Survivability in Hierarchical Telecommunications Networks Under Dual Homing, A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs, On the Steiner 2-edge connected subgraph polytope, A Network Design Problem with Two-Edge Matching Failures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Generalized Steiner problem in outerplanar networks
• The ellipsoid method and its consequences in combinatorial optimization
• Design of survivable networks
• An efficient approximation algorithm for the survivable network design problem
• The Steiner tree polytope and related polyhedra
• Tree polytope on 2-trees
• Two-edge connected spanning subgraphs and polyhedra
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• A primal-dual approximation algorithm for generalized Steiner network problems
• On two-connected subgraph polytopes
• The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs
• Steiner \(k\)-edge connected subgraph polyhedra
• Topology of series-parallel networks
• \(k\)-edge connected polyhedra on series-parallel graphs
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• The traveling salesman problem on a graph and some related integer polyhedra
• Generalized steiner problem in series-parallel networks
• Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The k-Edge-Connected Spanning Subgraph Polyhedron
• An Integer Polytope Related to the Design of Survivable Communication Networks
• Steiner 2-Edge Connected Subgraph Polytopes on Series-Parallel Graphs
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs
• On the dominant of the Steiner 2-edge connected subgraph polytope
• Steiner trees and polyhedra