MINIMUM K-SPANNING TREE

Next: MINIMUM DEGREE SPANNING TREE Up: Spanning Trees Previous: Spanning Trees Index

INSTANCE: Graph $G=\left(V,E\right)$ , an integer $k \leq n$ , and a weight function $w : E \rightarrow N$ .
SOLUTION: A k-spanning tree, i.e., a subtree T of G of at least k nodes.
MEASURE: The weight of the tree, i.e., $\sum_{e \in T}w(e)$ .
Good News: Approximable within 3 [184].
Bad News: APX-complete [Kann, --].
Comment: The restriction to points in the Euclidean plane admits a PTAS [33]. The analogous diameter and communication-cost k-spanning tree problems are not in APX [419].

Viggo Kann
2000-03-20