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

### MINIMUM K-SPANNING TREE

- INSTANCE: Graph , an integer , and a weight function .

- 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., .

- Good News: Approximable within 3 [172].

- Bad News: APX-complete [Kann, --].

- Comment: The restriction to points in the Euclidean plane admits a PTAS [31]. The analogous diameter and communication-cost k-spanning tree problems are not in APX [397].