An efficient approximation algorithm for the survivable network design problem

DOI10.1007/BF01585864zbMath0922.90140OpenAlexW2117754372MaRDI QIDQ1290632

Harold N. Gabow, Michel X. Goemans, David P. Williamson

Publication date: 18 October 1999

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

Full work available at URL: https://doi.org/10.1007/bf01585864

zbMATH Keywords

edge-connectivitypolynomial-time approximationsurvivable network designminimum-cost subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

A global optimization algorithm for reliable network design, Primal-dual approximation algorithms for the prize-collecting Steiner tree problem, A new approach for solving the network problems, On survivable network polyhedra, A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs, Network flow spanners, Approximation algorithms for minimum tree partition, On budget-constrained flow improvement.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Extracting maximal information about sets of minimum cuts
• A data structure for bicategories, with application to speeding up an approximation algorithm
• A primal-dual approximation algorithm for generalized Steiner network problems
• An 11/6-approximation algorithm for the network Steiner problem
• Multi-Terminal Network Flows
• On the structure of all minimum cuts in a network and applications
• Approximation Algorithms for Several Graph Augmentation Problems
• Odd Minimum Cut-Sets and b-Matchings
• Biconnectivity approximations and graph carvings
• Improved Approximations for the Steiner Tree Problem
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• A faster approximation algorithm for the Steiner problem in graphs