학술논문
Time-space tradeoffs for undirected graph traversal
Document Type
Conference
Author
Source
Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on. :429-438 vol.1 1990
Subject
Language
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