SRC Research Report 71
SRC Research Report 71
Aleliunas et al. posed the following question: "The reachability problem for undirected graphs can be solved in logspace and 0(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 conventional deterministic graph traversal algorithm. Is there a spectrum of time-space trade-offs between these extremes?" We answer this question in the affirmative for graphs with a linear number of edges by presenting an algorithm that is faster than the random walk by a factor essentially proportional to the size of its workspace. For denser graphs, our algorithm is faster than the random walk but the speed-up factor is smaller.
Back to the SRC Research Reports main page.