Next: MINIMUM DIAMETER SPANNING SUBGRAPH
Up: Spanning Trees
Previous: MAXIMUM LEAF SPANNING TREE
  Index
- INSTANCE:
Graph
,
length
for each
satisfying
the triangle inequality.
- SOLUTION:
A subset
such that
.
- MEASURE:
Cost of the minimum spanning tree of the subgraph induced by V'.
- Good News:
Approximable within 4 [225].
- Bad News:
APX-complete and not approximable within 2
for any
[225].
- Comment:
Also called Maximum Remote Minimum Spanning Tree.
Reduction from MAXIMUM INDEPENDENT SET.
As hard to approximate as MAXIMUM INDEPENDENT SET for non-metric graphs.
Approximable within 2.252 in the Euclidean metric, but not known
to be NP-complete.
MAXIMUM MINIMUM K-STEINER TREE is approximable within 3
and not approximable within 4/3
,
but approximable within 2.16
in the Euclidean metric.
MAXIMUM MINIMUM METRIC K-TSP is approximable within 3
and not approximable within 2
.
Viggo Kann
2000-03-20