Undirected connectivity in O(log/sup 1.5/n) space
Noam Nisan, Endre Szemerédi, Avi Wigderson · 1992
The authors present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log/sup 1.5/n) space. Thus, the recursive doubling technique of Savich (1970) which requires Theta (log/sup 2/n) space is not optimal for this problem.>