An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
From MaRDI portal
Publication:3012788
DOI10.1007/978-3-642-22006-7_2zbMath1332.68287OpenAlexW46202281MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items
Approximating subset \(k\)-connectivity problems ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ Multi-priority graph sparsification ⋮ Unnamed Item
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
This page was built for publication: An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
