- INSTANCE: Graph , cost function , set of terminals , a penalty function .
- SOLUTION: A tree in such that , .
- COST FUNCTION: .
- OBJECTIVE: Minimize.
*Approx.:*Approximable within for some [6].*Hardness:*NP-hard to approximate within 96/95 [36]. a PTAS for the special case when is a planar graph [29].

2015-04-27 Revision: 288 PDF version