Time-space tradeoffs for undirected graph traversal
Lists
Only you see this
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">></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...