Time-space lower bounds for directed s-t connectivity on JAG models
G. Barnes, Jeff A. Edmonds · 2002
Directed s-t connectivity is the problem of detecting whether there is a path from a distinguished vertex s to a distinguished vertex t in a directed graph. We prove time-space lower bounds of ST=/spl Omega/(n/sup 2//log n) and S/sup 1/2/T /spl Omega/(mn/sup 1/2/) for Cook and Rackoff's JAG model (1980), where n is the number of vertices and m the number of edges in the input graph, and S is the space and T the time used by the JAG. We also prove a time-space lower bound of S/sup 1/3/T=/spl Omega/(m/sup 2/3/n(2/3)) on the more powerful node-named JAG model of Poon (1993). These bounds approach the known upper bound of T=O(m) when S=/spl Theta/(n log n).>