 |
 |
32 of 32 |  |
 |
 |
MIT
Main Theorem
On any capacitated, undirected graph,
Algorithm RCA
»
runs in O
*
(n2)
time with simple structures
»
finds min-cut with probability
³ 1/log
n
Thus, O
(log n)
repetitions suffice to find
the minimum cut almost surely (failure
probability
10
-6
) in O(n² log²
n)
time.