MINIMUM DEGREE SPANNING TREE

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

INSTANCE: Graph $G=\left(V,E\right)$ .
SOLUTION: A spanning tree for G.
MEASURE: The maximum degree of the spanning graph.
Good News: Approximable with an absolute error guarantee of 1 [178].
Bad News: Not approximable within 3/2 $-\varepsilon$ for any $\varepsilon >0$ [182].
Comment: APX-intermediate unless the polynomial-hierarchy collapses [125]. The generalization of the problem to Steiner trees is also approximable with an absolute error guarantee of 1 [178].
Garey and Johnson: ND1

Viggo Kann
2000-03-20