 |
 |
3 of 18 |  |
 |
 |
MIT
l
s-t
min-cut dual to s-t
max-flow
l
min-cut by “all-pairs s-t min-cut”
»
[FF] Independent max
-flows:
O
*
(mn2)
time
»
[HO] Batched flows O
*
(mn)
time
»
[G] Pack spanning trees:
O
*
(mc)
time
l
Applies to directed graphs
Past Work: Flows