- INSTANCE: Graph , edge costs , set of terminals , positive integer .
- SOLUTION: A tree in such that , and (at most k Steiner nodes used).
- COST FUNCTION:
- OBJECTIVE: Minimize.
*Hardness:*NP-Hard to approximate within approximation ratio on undirected metric graphs [2]. NP-Hard to approximate within approximation ratio in the Euclidean plane [103].*Approx.:*Approximable within approximation ratio on undirected metric graphs [2]. Approximable within approximation ratio in the Euclidean plane [105].*Comment:*For the euclidean case, exact algorithms exist for and , with time complexity and respectively [8]. For the special case of the euclidean plane with no edges allowed between two Steiner points, a approximation algorithm exists [85].

2015-04-27 Revision: 288 PDF version