 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
l |
s-t flow: edge-disjoint packing of s-t paths
|
|
l |
s-t cut: a cut separating s and t
|
|
|
l |
[FF]: s-t max-flow = s-t min-cut
|
|
|
|
» |
max-flow
saturates all s-t min-cuts
|
|
|
|
» |
most efficient
way to find s-t min-cuts
|
|
|
l |
[GH]: min-cut is
“all-pairs” s-t min-cut
|
|
|
|
» |
find using n flow computations
|
|