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

### MAXIMUM LEAF SPANNING TREE

- INSTANCE: Graph .

- SOLUTION: A spanning tree for G.

- MEASURE: The number of leaves of the spanning tree.

- Good News: Approximable within 3 [343].

- Bad News: APX-complete [167].

- 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 [168]. 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 [102].

- Garey and Johnson: ND2