| 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… |
|||||||||||