- INSTANCE: Graph , set of terminals and a node weight function .
- SOLUTION: A tree in , such that , .
- COST FUNCTION:
- OBJECTIVE: Minimize.
*Approx.:*Approximable within approximation ratio [54]. Approximable within approximation ratio in the unweighted case [54]. The online version admits a polynomial time poly-logarithmic competitive online algorithm [91].*Hardness:*NP-Hard [90],[40]. NP-hard to approximate within for every [54].*Comment:*Node Weighted Steiner Tree in Unit Disk Graphs is approximable within approximation ratio . Admits a PTAS for the special case when the set of vertices is c-local.

A set of vertices is called c-local in a node weighted graph if in the minimum node weighted spanning tree for S, the weight of longest edge is at most c [84].

2015-04-27 Revision: 288 PDF version