Next:
MINIMUM MULTIWAY CUT
Up:
Cuts and Connectivity
Previous:
MINIMUM K-CUT
 
Index
M
INIMUM
V
ERTEX
K
-C
UT
I
NSTANCE:
Graph
, a set
of special vertices, and a weight function
, and an integer
k
.
S
OLUTION:
A vertex
k
-cut, i.e., a subset
of vertices such that their deletion from
G
disconnects each
from
for
.
M
EASURE:
The sum of the weight of the vertices in the cut, i.e.,
.
Good News:
Approximable within
[
188
].
Viggo Kann
2000-03-20