MIT
24
Main Theorem
lOn
any capacitated, undirected graph, Algorithm RCA
»runs
in O*(n2) time with simple structures
»finds
min-cut with probability ³ 1/log n
lThus,
O(log n)
repetitions suffice to find the minimum cut (failure probability 10-6) in O(n2 log2 n) time.