Next: MINIMUM VERTEX K-CUT
Up: Cuts and Connectivity
Previous: MINIMUM NETWORK INHIBITION ON
  Index
- INSTANCE:
Graph
,
a weight function
,
and an
integer
.
- SOLUTION:
A partition of V into k disjoint sets
.
- MEASURE:
The sum of the weight of the edges between the disjoint sets, i.e.,
- Good News:
Approximable within
[405].
- Comment:
Solvable in polynomial time O(|V|k2) for fixed k
[189].
If the sets in the partition are restricted to be of equal size, the
problem is approximable within
[405].
If the sets in the partition are restricted to be of specified sizes
and the weight function satisfies the triangle inequality, the
problem is approximable within 3 for any fixed k [201].
The unweighted problem admits a PTAS if every vertex has degree
[37].
Viggo Kann
1999-04-22