An approximation algorithm for minimum-cost vertex-connectivity problems

DOI10.1007/BF02523686zbMath0873.68076OpenAlexW2766198272MaRDI QIDQ679445

R. Ravi, David P. Williamson

Publication date: 9 October 1997

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsurvivable network design

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (13)

Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ On the minimum local-vertex-connectivity augmentation in graphs ⋮ Approximating node-connectivity augmentation problems ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems ⋮ Faster approximation algorithms for weighted triconnectivity augmentation problems ⋮ Approximating minimum size \{1,2\}-connected networks ⋮ A primal-dual approximation algorithm for the survivable network design problem in hypergraphs ⋮ Approximation algorithms for connectivity augmentation problems

Cites Work

• Design of survivable networks
• A minimum 3-connectivity augmentation of a graph
• On the optimal vertex-connectivity augmentation
• A primal-dual approximation algorithm for generalized Steiner network problems
• Improved data structures for fully dynamic biconnectivity
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Approximation Algorithms for Graph Augmentation
• Augmentation Problems
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances
• Improved Approximation Algorithms for Uniform Connectivity Problems
• THE MAXIMUM CONNECTIVITY OF A GRAPH
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An approximation algorithm for minimum-cost vertex-connectivity problems