This paper describes fast average-time algorithms for four graph connectivity problems. Algorithms that run in O(n) average time on n-vertex graphs are developed for finding connected components, strong components, and blocks. An O(m)-time algorithm to find a minimum spanning forest in an m-graph is also presented. The analysis of these algorithms uses the random graph model of Erdös and Renyi. All the algorithms are optimum to within a constant factor.
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics