Approximating fault-tolerant group-Steiner problems
From MaRDI portal
Publication:764316
DOI10.1016/j.tcs.2011.08.021zbMath1286.68502OpenAlexW2037655022MaRDI QIDQ764316
Zeev Nutov, Rohit Khandekar, Guy Kortsarz
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/2324/
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15)
Related Items (4)
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ Unnamed Item ⋮ On the hardness of full Steiner tree problems
Cites Work
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Inapproximability of survivable networks
- Approximating the weight of shallow Steiner trees
- An improved LP-based approximation for steiner tree
- Buy-at-Bulk Network Design with Protection
- Survivable network design with degree or order constraints
- Saving an epsilon
- Lower-Stretch Spanning Trees
- A Parallel Repetition Theorem
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- 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
- Approximating Steiner Networks with Node Weights
- A tight bound on approximating arbitrary metrics by tree metrics
- On the hardness of approximating spanners
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximating fault-tolerant group-Steiner problems
