An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
From MaRDI portal
Publication:494800
DOI10.1007/s00453-014-9869-5zbMath1328.68304OpenAlexW2163546498MaRDI QIDQ494800
Publication date: 2 September 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9869-5
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items
Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Unnamed Item ⋮ Approximating k-Connected m-Dominating Sets ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
Cites Work
- Unnamed Item
- Unnamed Item
- Approximating minimum-cost edge-covers of crossing biset-families
- 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
- Approximating subset \(k\)-connectivity problems
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Approximation Algorithms for Minimum-Cost $k\hbox{-}(S,T)$ Connected Digraphs
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- Approximation Algorithms for Network Design with Metric Costs
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- Improved Approximation Algorithms for Uniform Connectivity Problems
- An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem
- Approximating Rooted Steiner Networks
- An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
- Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
- Approximating Steiner Networks with Node-Weights
- Steiner Tree Approximation via Iterative Randomized Rounding
- Approximating k-node Connected Subgraphs via Critical Graphs
This page was built for publication: An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
