Time-space tradeoffs for undirected graph traversal

Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa

Abstract

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>
BibTeX
@inproceedings{beame1990time,
  author = {Paul Beame and Allan Borodin and Prabhakar Raghavan and Walter L. Ruzzo and Martin Tompa},
  title = {{Time-space tradeoffs for undirected graph traversal}},
  booktitle = {FOCS},
  year = {1990},
  doi = {10.1109/fscs.1990.89563},
}

Loading related content...

Figure