Title :
Time-space tradeoffs for undirected graph traversal
Author :
Beame, Paul ; Borodin, Allan ; Raghavan, Prabhakar ; Ruzzo, Walter L. ; Tompa, Martin
Author_Institution :
Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
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
Keywords :
automata theory; graph theory; deterministic model; jumping automata; probabilistic upper bound; quadratic lower bound; time-space tradeoff; undirected graph traversal; Automata; Computational complexity; Computational modeling; Computer science; Contracts; Councils; Inspection; Polynomials; Turing machines; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89563
