MIT
10
Max-flow/Min-cut
ls-t flow: edge-disjoint packing
of s-t paths
ls-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