An Algorithm for Determining Whether the Connectivity of a Graph is at Least k
Shimon Even · SIAM Journal on Computing · 1975
The algorithm presented in this paper is for testing whether the connectivity of a large graph of n vertices is at least k. First the case of undirected graphs is discussed, and then it is shown that a variation of this algorithm works for directed graphs. The number of steps the algorithm requires, in case $k < \sqrt n $, is bounded by $O(kn^3 )$.