Next: MAXIMUM LEAF SPANNING TREE Up: Spanning Trees Previous: MINIMUM DEGREE SPANNING TREE Index

### MINIMUM GEOMETRIC 3-DEGREE SPANNING TREE

- INSTANCE: Set of points in the plane.

- SOLUTION: A spanning tree T for P in which no vertex has degree larger than 3.

- MEASURE: The total weight of the spanning tree, i.e., , where d(u,v) is the Euclidean distance between u and v.

- Good News: Admits a PTAS [31].

- Comment: The 4-degree spanning tree problem also admits a PTAS, but the NP-hardness of the problem is open [31]. The 5-degree problem is polynomial-time solvable. In d-dimensional Euclidean space for the 3-degree spanning tree problem is approximable within 5/3. [299].

  The generalization to a graph with metric weight function and for each vertex Ưa degree bound d(v) is called MINIMUM BOUNDED DEGREE SPANNING TREE and is approximable within , where dT(v) is the initial degree of v [146].