MIT
71
s-t Min-Cuts
lRecall: if G has
min-cut c, then in G(r/c) all cuts approximate their expected values
to within
e.
lApplications:
Min-cut in
O*(mc) time [G]
Approximate/exact in
O*((m/c) c) =O*(m)
s-t min-cut
of
value v in O*(mv)
Approximate in
O*(mv/c) time
lTrouble
if c is
small and v large.