** Next:** MAXIMUM BALANCED CONNECTED PARTITION
** Up:** Covering and Partitioning
** Previous:** MINIMUM CLIQUE PARTITION
** Index**

- INSTANCE:
Graph
,
and a weight function
.
- SOLUTION:
A
*k*-capacitated tree partition of *G*, i.e., a collection of vertex disjoint
subsets
of *E* such that, for each *i*, the subgraph induced
by
is a tree of at least *k* vertices.
- MEASURE:
The weight of the partition, i.e.,
.

*Good News:*
Approximable within
[197].
*Comment:*
The variation in which the trees must contain exactly *k* vertices and the
triangle inequality is satisfied is approximable within
.
Similar results hold for the corresponding cycle and path partitioning problems
with the triangle inequality [197].
Variation in which the trees must contain exactly *k* vertices and the
objective is to minimize
is not in APX,
but if the triangle inequality is satisfied it is approximable within
[211].
The variation in which the number *m* of trees is fixed, the trees'
sizes are exactly specified, and the triangle inequality is satisfied
is approximable within *2p-1* [212].

*Viggo Kann*

*2000-03-20*