Approximating node-connectivity augmentation problems
From MaRDI portal
Publication:2429349
DOI10.1007/s00453-011-9538-xzbMath1250.68068OpenAlexW2149935452MaRDI QIDQ2429349
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9538-x
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (6)
Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating subset \(k\)-connectivity problems ⋮ Approximating minimum cost source location problems with local vertex-connectivity demands ⋮ Approximating source location and star survivable network problems ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ Approximating Source Location and Star Survivable Network Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for directed Steiner forest
- An approximation algorithm for minimum-cost vertex-connectivity problems
- A factor 2 approximation algorithm for the generalized Steiner network problem
- On shredders and vertex connectivity augmentation
- 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
- A note on the vertex-connectivity augmentation problem
- Approximating node connectivity problems via set covers
- Independence free graphs and vertex connectivity augmentation
- On the optimal vertex-connectivity augmentation
- Minimal edge-coverings of pairs of sets
- Approximating rooted connectivity augmentation problems
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Design networks with bounded pairwise distance
- Augmenting undirected node-connectivity by one
- Approximation Algorithms for Network Design with Metric Costs
- Polylogarithmic inapproximability
- Approximating Node-Connectivity Augmentation Problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- Approximation Algorithms for Directed Steiner 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
This page was built for publication: Approximating node-connectivity augmentation problems
