Next: Internal Steiner Tree
Up: Steiner Tree Problems
Previous: -Dense Steiner Tree Problem
, cost function
, set of terminals
- COST FUNCTION:
be approximated within a factor less than
. This bound also applies to the node-weighted case. 
Approximable within approximation ratio 2.458 on metric instances . Can be improved to 1.9329 using the algorithm presented in .
For the special case of unit disc graphs, a 20-approximation was given by Biniaz et al. . For the euclidean bottleneck version of this problem, an exact solution can be computed in polynomial time .
2015-04-27 Revision: 288 PDF version