Next:
ND16 MINIMUM K-CUT
Up:
Cuts and Connectivity
Previous:
ND14 MAXIMUM K-CUT
ND15 M
INIMUM
N
ETWORK
I
NHIBITION
ON
P
LANAR
G
RAPHS
I
NSTANCE
: Planar graph
, capacity function
, destruction cost function
, and budget
B
.
S
OLUTION
: An attack strategy to the network, i.e., a function
such that
.
M
EASURE
: The capability left in the damaged network, i.e., the minimum cut in
G
with capacity
c'
defined as
.
Good News:
Admits an FPTAS [
292
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
, capacity function
,
destruction cost function
, and budget
B
.
such that
.
.