An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem

DOI10.1007/s00453-014-9869-5zbMath1328.68304OpenAlexW2163546498MaRDI QIDQ494800

Bundit Laekhanukit

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

zbMATH Keywords

algorithmsnetwork designgraph connectivityapproximation algorithmssubset \(k\)-connected subgraph

Mathematics Subject Classification ID

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