| Enumeration |
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | RCA as stated
has constant probability |
|||||||||||
| of finding any
given min-cut |
||||||||||||
| l | If run O(log n) times, probability of |
|||||||||||
| missing a min-cut
drops to 1/n3 |
||||||||||||
| l | But
only n2 min-cuts |
|||||||||||
| l | So, probability
miss any at most 1/n |
|||||||||||
| l | So, with
probability 1-1/n, find all |
|||||||||||
| » | O(n2 log3 n) time |
|||||||||||