Next:
ND18 MINIMUM MULTIWAY
Up:
Cuts and Connectivity
Previous:
ND16 MINIMUM K-CUT
ND17 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
[
127
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997