- INSTANCE: Graph , edge costs , set of terminals .
- SOLUTION: A tree in G such that , .
- COST FUNCTION:
- OBJECTIVE: Minimize.
*Approx.:*Approximable within [21] (see also [98],[73]).*Hardness:*NP-hard to approximate within an approximation ratio 96/95 [36].*Comment:*Admits a PTAS in the special case when G is a planar graph [19]. Solvable exactly in time , where is the number of vertices, the number of terminals and the number of edges in the graph [46],[68].

2015-04-27 Revision: 288 PDF version