Approximation algorithms for the covering Steiner problem
From MaRDI portal
Publication:4537631
DOI10.1002/rsa.10038zbMath1017.68090OpenAlexW1970076003MaRDI QIDQ4537631
R. Ravi, Aravind Srinivasan, Goran Konjevod
Publication date: 1 July 2002
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.10038
Related Items
Approximation algorithms for requirement cut on graphs ⋮ The relation of connected set cover and group Steiner tree ⋮ The minimum vulnerability problem ⋮ Meet and merge: approximation algorithms for confluent flows ⋮ The polymatroid Steiner problems ⋮ A greedy approximation algorithm for the group Steiner problem
Cites Work
- A 2.5-factor approximation algorithm for the \(k\)-MST problem
- Geometric algorithms and combinatorial optimization
- On approximating planar metrics by tree metrics.
- Poisson approximation for large deviations
- Weighted k‐cardinality trees: Complexity and polyhedral structure
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Spanning Trees—Short or Small
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item