An efficient approximation algorithm for the survivable network design problem
type: Item
instance of: scholarly article
title: An efficient approximation algorithm for the survivable network design problem
zbMATH Open document ID: 0922.90140
DOI: 10.1007/BF01585864
author: Harold N. Gabow
author: Michel X. Goemans
author: David P. Williamson
published in: Mathematical Programming. Series A. Series B
publication date: 1999-10-18T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1294683
zbMATH Keywords: survivable network design
zbMATH Keywords: minimum-cost subgraph
zbMATH Keywords: edge-connectivity
zbMATH Keywords: polynomial-time approximation
MaRDI profile type: Publication
cites work: When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
cites work: Improved Approximations for the Steiner Tree Problem
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
cites work: Q4234132
cites work: Q3128880
cites work: Survivable networks, linear programming relaxations and the parsimonious property
cites work: A General Approximation Technique for Constrained Forest Problems
cites work: Multi-Terminal Network Flows
cites work: Q4845372
cites work: Extracting maximal information about sets of minimum cuts
cites work: Biconnectivity approximations and graph carvings
cites work: Q4234131
cites work: A data structure for bicategories, with application to speeding up an approximation algorithm
cites work: A faster approximation algorithm for the Steiner problem in graphs
cites work: Odd Minimum Cut-Sets and b-Matchings
cites work: On the structure of all minimum cuts in a network and applications
cites work: A primal-dual approximation algorithm for generalized Steiner network problems
cites work: An 11/6-approximation algorithm for the network Steiner problem
full work available at URL: https://doi.org/10.1007/bf01585864
OpenAlex ID: W2117754372
Recommended article: Q4234132
Recommended article: Fast Approximation Algorithms for the Generalized Survivable Network Design Problem
Recommended article: Fast exact algorithms for survivable network design with uniform requirements
Recommended article: Q4737224
Recommended article: Q4548331
Recommended article: A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
Recommended article: An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
Recommended article: An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
Recommended article: Q2762526
description: scientific article; zbMATH DE number 1294683