Next: MAXIMUM MINIMUM METRIC K-SPANNING
Up: Spanning Trees
Previous: MINIMUM GEOMETRIC 3-DEGREE SPANNING
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A spanning tree for G.
- MEASURE:
The number of leaves of the spanning tree.
- Good News:
Approximable within 3 [362].
- Bad News:
APX-complete [179].
- Comment:
Other problems which aim at finding spanning trees that maximize a
single objective function have been considered. In particular, the
problems of finding a spanning tree that has maximum diameter, or
maximum height with respect to a specified root are not in APX, the
problems of finding a spanning tree that has maximum sum of the
distances between all pairs of vertices, or maximum sum of the
distances from a specified root, are not in PTAS [180].
The problem of finding a spanning tree that maximizes the number of paths
that connect pairs of vertices and pass through a common arc is
approximable within 1.072 [110].
- Garey and Johnson: ND2
Viggo Kann
2000-03-20