On the approximability of dense Steiner problems
From MaRDI portal
Publication:396661
DOI10.1016/j.jda.2013.06.005zbMath1335.05173MaRDI QIDQ396661
Publication date: 13 August 2014
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2013.06.005
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A primal-dual approximation algorithm for the Steiner forest problem
- Approximating Subdense Instances of Covering Problems
- An improved LP-based approximation for steiner tree
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Polylogarithmic inapproximability
- Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
- Steiner's problem in graphs and its implications
- The steiner problem in graphs