Approximating subset \(k\)-connectivity problems
From MaRDI portal
Publication:2376789
DOI10.1016/j.jda.2012.08.001zbMath1281.68237OpenAlexW1975776599MaRDI QIDQ2376789
Publication date: 24 June 2013
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2012.08.001
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (11)
Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ Survivable network activation problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Multi-priority graph sparsification ⋮ Approximating k-Connected m-Dominating Sets ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems ⋮ Approximating Survivable Networks with Minimum Number of Steiner Points
Cites Work
- Unnamed Item
- Tight approximation algorithm for connectivity augmentation problems
- Inapproximability of survivable networks
- An application of submodular flows
- On the ratio of optimal integral and fractional covers
- Approximating node connectivity problems via set covers
- On the optimal vertex-connectivity augmentation
- Minimal edge-coverings of pairs of sets
- Approximating node-connectivity augmentation problems
- Approximating rooted connectivity augmentation problems
- An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
- Augmenting Undirected Node-Connectivity by One
- Approximation Algorithms for Network Design with Metric Costs
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
- Improved Approximation Algorithms for Uniform Connectivity 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: Approximating subset \(k\)-connectivity problems
