A PTAS for the Steiner Forest Problem in Doubling Metrics
From MaRDI portal
Publication:5376440
DOI10.1137/16M1107206zbMath1398.68677arXiv1608.06325OpenAlexW2889530899MaRDI QIDQ5376440
T-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang
Publication date: 18 September 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1608.06325
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- The Steiner tree problem on graphs: inapproximability results
- Steiner minimal trees for regular polygons
- Euclidean prize-collecting Steiner forest
- An improved LP-based approximation for steiner tree
- Greedy Algorithms for Steiner Forest
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Bypassing the embedding
- Polylogarithmic inapproximability
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
- Steiner Minimal Tree for Points on a Circle
- Plongements lipschitziens dans ${\bbfR}\sp n$
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- The traveling salesman problem
- Advances in metric embedding theory
- Geometry of cuts and metrics
This page was built for publication: A PTAS for the Steiner Forest Problem in Doubling Metrics
