Next: MAXIMUM MINIMUM METRIC K-SPANNING
Up: Spanning Trees
Previous: MINIMUM GEOMETRIC 3-DEGREE SPANNING
A spanning tree for G.
The number of leaves of the spanning tree.
- Good News:
Approximable within 3 .
- Bad News:
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 .
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 .
- Garey and Johnson: ND2