Next: MINIMUM DIAMETER SPANNING SUBGRAPH
Up: Spanning Trees
Previous: MAXIMUM LEAF SPANNING TREE
the triangle inequality.
such that .
Cost of the minimum spanning tree of the subgraph induced by V'.
- Good News:
Approximable within 4 .
- Bad News:
APX-complete and not approximable within 2
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.