Next: Terminal Steiner Tree
Up: Steiner Tree Problems
Previous: Euclidean Steiner Tree Problem
, set of terminals
such that each
has at least
A Steiner tree
- COST FUNCTION:
, there exists a PTAS for the
-Dense Steiner Tree Problem
. This also yields existence of an efficient PTAS ).
-Subdense Steiner Tree Problem where every terminal has at least
neighbors also admits a PTAS for
So far the problem is not known to be NP-hard in the exact setting.
2015-04-27 Revision: 288 PDF version