Next: MINIMUM GEOMETRIC 3-DEGREE SPANNING
Up: Spanning Trees
Previous: MINIMUM K-SPANNING TREE
  Index
- 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 [178].
- Bad News:
Not approximable within 3/2
for any
[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