TRADING SPACE FOR TIME IN UNDIRECTED S-T CONNECTIVITY

Aleliunas et al. [20th Annual Symposium on Foundations of Computer Sci ence, IEEE Computer Society Press, Los Alamitos, CA, 1979, pp. 218-223 ] posed the following question: ''The reachability problem for undirec ted graphs can be solved in log space and O(mn) time [m is the number of edges and n is the number of vertices] by a probabilistic algorithm that simulates a random walk, or in linear time and space by a conven tional deterministic graph traversal algorithm. Is there a spectrum of time-space trade-offs between these extremes?'' This question is answ ered in the affirmative for sparse graphs by presentation of an algori thm that is faster than the random walk by a factor essentially propor tional to the size of its workspace. For denser graphs, this algorithm is faster than the random walk but the speed-up factor is smaller.