Greg Barnes

STOC Conference 1993 Conference Paper

Short random walks on graphs

• Greg Barnes
• Uriel Feige

FOCS Conference 1993 Conference Paper

Time-Space Bounds for Directed s-t Connectivity on JAG Models (Extended Abstract)

• Greg Barnes
• Jeff Edmonds

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). >

STOC Conference 1991 Conference Paper

Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (Extended Abstract)

• Greg Barnes
• Walter L. Ruzzo