Next: MAXIMUM BALANCED CONNECTED PARTITION
Up: Covering and Partitioning
Previous: MINIMUM CLIQUE PARTITION
and a weight function
A k-capacitated tree partition of G, i.e., a collection of vertex disjoint
of E such that, for each i, the subgraph induced
is a tree of at least k vertices.
The weight of the partition, i.e.,
- Good News:
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 .
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
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 .