{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:13:51Z","timestamp":1787390031976,"version":"build-2736575974"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Directed s-t connectivity is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph. We present the first known deterministic sublinear space, polynomial time algorithm for directed s-t connectivity. For n-vertex graphs, our algorithm can use as little as $n\/2^{\\Theta(\\sqrt{\\log n})}$ space while still running in polynomial time.<\/jats:p>","DOI":"10.1137\/s0097539793283151","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1273-1282","source":"Crossref","is-referenced-by-count":24,"title":["A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity"],"prefix":"10.1137","volume":"27","author":[{"given":"Greg","family":"Barnes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan F.","family":"Buss","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Walter L.","family":"Ruzzo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Greg Barnes, Jonathan Buss, Walter Ruzzo, Baruch Schieber, A sublinear space, polynomial time algorithm for directed s\u2010t connectivity, IEEE Comput. Soc. Press, Los Alamitos, CA, 1992, 27\u20133394i:68232","DOI":"10.1109\/SCT.1992.215378"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"G. Barnes and J. A. Edmonds,\n                      Time\u2010space lower bounds for directed s\u2010t connectivity on JAG models\n                      , in Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 228\u2013237.","DOI":"10.1109\/SFCS.1993.366864"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202039"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"S. A. Cook,\n                      Deterministic CFL\u2019s are accepted simultaneously in polynomial time and log squared space\n                      , in Conference Record of the 11th Annual ACM Symposium on Theory of Computing, Atlanta, GA, 1979, pp. 338\u2013345. See also [14].","DOI":"10.1145\/800135.804426"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0209048"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"J. A. Edmonds and C. K. Poon,\n                      A nearly optimal time\u2010space lower bound for directed st\u2010connectivity on the NNJAG model\n                      , in Proc. 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 147\u2013156.","DOI":"10.1145\/225058.225103"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90058-5"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205052"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"N. Nisan, E. Szemer\u00e9di, and A. Wigderson,\n                      Undirected connectivity in O(log1.5n) space\n                      , in Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 1992, pp. 24\u201329.","DOI":"10.1109\/SFCS.1992.267822"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"C. K. Poon,\n                      Space bounds for graph connectivity problems on node\u2010named JAGs and node\u2010oriented JAGs\n                      , in Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 218\u2013227.","DOI":"10.1109\/SFCS.1993.366865"},{"key":"R11","unstructured":"C. K. Poon,\n                      On the Complexity of the st\u2010Connectivity Problem\n                      , Ph.D. Thesis, University of Toronto, 1996."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0211010"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80049-7"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Avi Wigderson, The complexity of graph connectivity, Lecture Notes in Comput. Sci., Vol. 629, Springer, Berlin, 1992, 112\u201313294j:05130","DOI":"10.1007\/3-540-55808-X_10"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793283151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:09Z","timestamp":1787336049000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793283151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":15,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793283151"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793283151","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}