Next:
ND5 MAXIMUM MINIMUM
Up:
Spanning Trees
Previous:
ND3 MINIMUM GEOMETRIC
-
I
NSTANCE
:
Graph
.
-
S
OLUTION
:
A spanning tree for
G
.
-
M
EASURE
:
The number of leaves of the spanning tree.
-
Good News:
Approximable within 3 [
261
].
-
Bad News:
A
PX
-complete [
118
].
-
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 A
PX
, 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, while the problem of
finding a spanning tree that maximizes the number of paths which
connect pairs of vertices and pass through a common arc is
approximable within 9/8 [
119
].
-
Garey and Johnson:
ND2
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997