Next: MINIMUM GEOMETRIC 3-DEGREE SPANNING Up: Spanning Trees Previous: MINIMUM K-SPANNING TREE Index

### MINIMUM DEGREE SPANNING TREE

- INSTANCE: Graph .

- SOLUTION: A spanning tree for G.

- MEASURE: The maximum degree of the spanning graph.

- Good News: Approximable with an absolute error guarantee of 1 [166].

- Bad News: Not approximable within 3/2 for any [170].

- Comment: APX-intermediate unless the polynomial-hierarchy collapses [117]. The generalization of the problem to Steiner trees is also approximable with an absolute error guarantee of 1 [166].

- Garey and Johnson: ND1