An efficient approximation algorithm for the survivable network design problem
From MaRDI portal
Publication:1290632
DOI10.1007/BF01585864zbMATH Open0922.90140OpenAlexW2117754372MaRDI QIDQ1290632FDOQ1290632
Authors: 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
Recommendations
- scientific article; zbMATH DE number 1263260
- Fast Approximation Algorithms for the Generalized Survivable Network Design Problem
- Fast exact algorithms for survivable network design with uniform requirements
- Fast exact algorithms for survivable network design with uniform requirements
- scientific article; zbMATH DE number 2086687
- scientific article; zbMATH DE number 1788731
- A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
- An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
- An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
- scientific article; zbMATH DE number 1688385
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- An 11/6-approximation algorithm for the network Steiner problem
- Title not available (Why is that?)
- Improved Approximations for the Steiner Tree Problem
- A General Approximation Technique for Constrained Forest Problems
- Title not available (Why is that?)
- Biconnectivity approximations and graph carvings
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Multi-Terminal Network Flows
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Odd Minimum Cut-Sets and b-Matchings
- A faster approximation algorithm for the Steiner problem in graphs
- On the structure of all minimum cuts in a network and applications
- Survivable networks, linear programming relaxations and the parsimonious property
- Title not available (Why is that?)
- Approximation Algorithms for Several Graph Augmentation Problems
- A primal-dual approximation algorithm for generalized Steiner network problems
- Title not available (Why is that?)
- Extracting maximal information about sets of minimum cuts
- A data structure for bicategories, with application to speeding up an approximation algorithm
Cited In (23)
- A note on Rooted Survivable Networks
- Survivable networks, linear programming relaxations and the parsimonious property
- Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
- Inapproximability of survivable networks
- Approximation algorithms for minimum tree partition
- Approximating survivable networks with \(\beta \)-metric costs
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- A global optimization algorithm for reliable network design
- Network flow spanners
- Additive Approximation for Bounded Degree Survivable Network Design
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- Using a hybrid of exact and genetic algorithms to design survivable networks
- Inapproximability of Survivable Networks
- A factor 2 approximation algorithm for the generalized Steiner network problem
- On budget-constrained flow improvement.
- A new approach for solving the network problems
- Stochastic survivable network design problems: theory and practice
- Fast Approximation Algorithms for the Generalized Survivable Network Design Problem
- Complexity of column generation in network design with path-based survivability mechanisms
- Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems
- The \(k\)-path tree matroid and its applications to survivable network design
- On survivable network polyhedra
This page was built for publication: An efficient approximation algorithm for the survivable network design problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1290632)
