Next: MINIMUM MULTIWAY CUT
Up: Cuts and Connectivity
Previous: MINIMUM K-CUT
  Index
- INSTANCE:
Graph
,
a set
of special
vertices, and a weight function
,
and an integer k.
- SOLUTION:
A vertex k-cut, i.e., a subset
of vertices such that
their deletion from G disconnects each si from ti for
.
- MEASURE:
The sum of the weight of the vertices in the cut, i.e.,
.
- Good News:
Approximable within
[176].
Viggo Kann
1999-04-22