 |
 |
5 of 18 |  |
 |
 |
MIT
This work: Tree Packing
l
s-t
max-flow yields s-t min-cut
»
Pack
s-t
paths
»
packing saturates s-t min
-cut
l
Tree packing gives global min-cut
»
Pack trees (“global flows”)
»
saturates global min-cut
l
Result: min-cut in O
*
(m) time