- INSTANCE: Graph , edge costs , set of terminals , positive integer , a penalty function .
- SOLUTION: Tree in such that , and (at most k Steiner nodes used).
- COST FUNCTION:
- OBJECTIVE: Minimize.
*Hardness:*NP-Hard to approximate within on undirected metric graphs [2].*Approx.:*Approximable within approximation ratio on undirected metric graphs [63].

2015-04-27 Revision: 288 PDF version