Next: MINIMUM CLIQUE COVER
Up: Covering and Partitioning
Previous: MINIMUM K-CAPACITATED TREE PARTITION
  Index
- INSTANCE:
Connected graph G=(V, E), nonnegative vertex-weight function
.
- SOLUTION:
A partition (V1, V2) of V into nonempty disjoint sets
V1 and V2 such that the subgraphs of G induced by
V1 and V2 are connected.
- MEASURE:
Balance of the partition, i.e.,
,
where
.
- Good News:
Approximable within 4/3 [102].
- Bad News:
Not approximable with an absolute error guarantee of
for any
[102].
- Comment:
Variation in which the objective function is
is
approximable within
[102].
Viggo Kann
1999-04-22