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