@inproceedings{5e5b6538442b4d328c05cb44772c18ad,

title = "A sublinear space, polynomial time algorithm for directed s-t connectivity",

abstract = "A deterministic sublinear space, polynomial-time algorithm for directed s-t connectivity, which is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph, is presented. For n-vertex graphs, the algorithm can use as little as n/2Θ(√log n) space while still running in polynomial time.",

author = "Greg Barnes and Buss, {Jonathan F.} and Ruzzo, {Walter L.} and Baruch Schieber",

year = "1992",

language = "English (US)",

isbn = "081862955X",

series = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference",

publisher = "Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516",

pages = "27--33",

booktitle = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference",

note = "Proceedings of the Seventh Annual Structure in Complexity Theory Conference ; Conference date: 22-06-1992 Through 25-06-1992",

}