Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (Extended Abstract) - Greg Barnes; Walter L. Ruzzo (STOC, 1991)

A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity - Greg Barnes; Jonathan F. Buss; Walter L. Ruzzo; Baruch Schieber (SCT, 1992)

Time-Space Bounds for Directed s-t Connectivity on JAG Models (Extended Abstract) - Greg Barnes; Jeff Edmonds (FOCS, 1993)

A Method for Implementing Lock-Free Shared-Data Structures. - Greg Barnes (SPAA, 1993)

Short Random Walks on Graphs. - Greg Barnes; Uriel Feige (SIAM J. Discret. Math., 1996)

Undirected s-t Connectivity in Polynomial Time and Sublinear Space. - Greg Barnes; Walter L. Ruzzo (Comput. Complex., 1997)

A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. - Greg Barnes; Jonathan F. Buss; Walter L. Ruzzo; Baruch Schieber (SIAM J. Comput., 1998)

Time-Space Lower Bounds for Directed st-Connectivity on Graph Automata Models. - Greg Barnes; Jeff Edmonds (SIAM J. Comput., 1998)