Next: MINIMUM K-CUT
Up: Cuts and Connectivity
Previous: MAXIMUM K-CUT
  Index
- INSTANCE:
Planar graph
,
capacity function
,
destruction cost function
,
and budget B.
- SOLUTION:
An attack strategy to the network, i.e., a function
such that
.
- MEASURE:
The capability left in the damaged network, i.e., the minimum cut in G with
capacity c' defined as
.
- Good News:
Admits an FPTAS [402].
Viggo Kann
2000-03-20