Time-space tradeoffs for undirected graph traversal
Paul W. Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa · 2002
Time-space tradeoffs for traversing undirected graphs are proved. One of these tradeoffs is a quadratic lower bound on a deterministic model that closely matches the probabilistic upper bound of A.Z. Broder et al. (1989). The models used are variants of S.A. Cook and C.W. Rackoff's (1980) jumping automata for graphs. Some open problems are stated.>