MIT
30
Enumeration
lRCA
as stated has constant probability of finding any given
min-cut
lIf
run O(log n) times, probability of missing
a min-cut drops to 1/n3
lBut
only n2 min-cuts
lSo,
probability miss any at most 1/n
lSo,
with probability 1-1/n, find all
»O(n2 log3 n)
time