Approximation algorithms for the covering Steiner problem

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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