An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
From MaRDI portal
Publication:3012788
DOI10.1007/978-3-642-22006-7_2zbMath1332.68287MaRDI QIDQ3012788
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_2
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
05C40: Connectivity
Related Items
Unnamed Item, Approximating minimum-cost edge-covers of crossing biset-families, Approximating subset \(k\)-connectivity problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- An approximation algorithm for minimum-cost vertex-connectivity problems
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A note on Rooted Survivable Networks
- Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- An improved LP-based approximation for steiner tree
- Approximation Algorithms for Network Design with Metric Costs
- A Graph Reduction Step Preserving Element-Connectivity and Applications
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
- Approximating k-node Connected Subgraphs via Critical Graphs
