Time-space tradeoffs for graph S-T connectivity
Gregory Barnes · 1992
The problem of graph s-t connectivity, determining whether two vertices s and t in a graph are in the same connected component, is a fundamental problem in computational complexity theory. Determining the space complexity of s-t connectivity either for directed graphs (stcon) or for undirected graphs (ustcon) would tell us a great deal about the relationships among deterministic, nondeterministic, and probabilistic logarithmic space bounded complexity classes. A fruitful intermediate step to determining the space complexity of stcon and ustcon is to explore time-space tradeoffs for the problems: the simultaneous time and space requirements of algorithms for connectivity. Prior to this work, all deterministic connectivity algorithms that used less than linear space (the space bound for well-known algorithms such as ...