Applications of the theory of random graphs to average algorithm performance analysis
Henry Koch Dewitt · 1979
In the past, most algorithmic analysis has centered On the determination of the worst case performance. In real world applications, the average performance of an algorithm is of far more interest. In this paper, we use the results of the theory of random graphs to aid in the design and analysis of more efficient graph theoretic optimization algorithms. The results show that the theory of random graphs can be a powerful tool in the analysis of average algorithm performance.