The actual run times for finding the minimum cut of a randomly generated graph are shown below.
- A probabilistic algorithm can be run multiple times to achieve a higher probability of success.
- By increasing the probability of producing the correct answer on each iteration, the total number of iterations is decreased. This results in HUGE overall run time savings.
Click here for details on generating actual run time data