MIT
40
Min-cut Duality
l[Edmonds]:
min-cut=max tree packing
»convert
to directed graph
»“source”
vertex s (doesn’t matter which)
»spanning
trees directed away from s
l[Gabow]
“augmenting trees”
»add
a tree in O*(m) time
»min-cut
c
(via max packing) in O*(mc)
»great if m and c are small…