{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:54:23Z","timestamp":1787385263616,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Directed st-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 = \\Omega({n^{2} \\log n \\over \\log (n \\log n\/S)})$ and $S^{1 \\over 2}T = \\Omega(m (n \\log n)^{1 \\over 2})$ for directed st-connectivity on Cook and Rackoff's jumping automaton for graphs (JAG) model [SIAM J. Comput., 9(1980), pp. 636--652], where n is the number of vertices and m the number of edges in the input graph, S is the space, and T the time used by the JAG. These lower bounds are simple and elegant, they approach the known upper bound of T = O(m) when S approaches $\\Theta(n \\log n)$, and they are the first time--space tradeoffs for JAGs with an unrestricted number of jumping pebbles.<\/jats:p>","DOI":"10.1137\/s0097539795294402","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1190-1202","source":"Crossref","is-referenced-by-count":3,"title":["Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models"],"prefix":"10.1137","volume":"27","author":[{"given":"Greg","family":"Barnes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeff A.","family":"Edmonds","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"D. Achlioptas, J. Edmonds, and C. K. Poon,\n                      Tight lower bounds for st\u2010connectivity on NNJAGs\n                      , SIAM J. Comput., to appear."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Romas Aleliunas, Richard Karp, Richard Lipton, L\u00e1szl\u00f3 Lov\u00e1sz, Charles Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, IEEE, New York, 1979, 218\u201322382h:68084","DOI":"10.1109\/SFCS.1979.34"},{"key":"R3","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":"R4","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 Symposium on Foundations of Computer Science, IEEE, Palo Alto, CA, Nov. 1993, pp. 228\u2013237.","DOI":"10.1109\/SFCS.1993.366864"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"G. Barnes and U. Feige,\n                      Short random walks on graphs\n                      , in Proc. 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, May 1993, pp. 728\u2013737.","DOI":"10.1145\/167088.167275"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"G. Barnes and W. L. Ruzzo,\n                      Deterministic algorithms for undirected s\u2010t connectivity using polynomial time and sublinear space\n                      , in Proc. 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, May 1991, pp. 43\u201353; Department of Computer Science and Engineering, University of Washington Tech. report 91\u201006\u201002; Comput. Complexity 6 (1996\u201397), pp. 1\u201328.","DOI":"10.1145\/103418.103430"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0085"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"P. Berman and J. Simon,\n                      Lower bounds on graph threading by probabilistic machines\n                      , in Proc. 24th Annual Symposium on Foundations of Computer Science, IEEE, Tucson, AZ, Nov. 1983, pp. 304\u2013311.","DOI":"10.1109\/SFCS.1983.31"},{"key":"R9","unstructured":"A. Borodin,\n                      \n                        Structured\n                        vs\n                        . general models in computational complexity\n                      \n                      , L\u2019Enseignement Math\u00e9matique, 28 (1982)."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90046-L"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0209048"},{"key":"R12","unstructured":"J. A. Edmonds,\n                      Time\u2010Space Lower Bounds for Undirected and Directed ST\u2010Connectivity on JAG Models\n                      , Ph.D. thesis, Department of Computer Science, University of Toronto, Aug. 1993."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. A. Edmonds,\n                      Time\u2010space trade\u2010offs for undirected st\u2010connectivity on a JAG\n                      , in Proc. 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, May 1993, pp. 718\u2013727; SIAM J. Comput., to appear.","DOI":"10.1145\/167088.167272"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"J. Edmonds and C. K. Poon,\n                      A nearly optimal time\u2010space lower bound for graph connectivity problem on NNJAG model\n                      , in Proc. 27th Annual ACM Symposium on Theory of Computing, 1995, pp. 147\u2013156.","DOI":"10.1145\/225058.225103"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90058-5"},{"key":"R17","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 Symposium on Foundations of Computer Science, IEEE, Pittsburgh, PA, Oct. 1992, pp. 24\u201329.","DOI":"10.1109\/SFCS.1992.267822"},{"key":"R18","unstructured":"C. K. Poon,\n                      Space bounds for graph connectivity problems on node\u2010named JAGs and node\u2010oriented JAGs\n                      , in Proc. 34th Annual Symposium on Foundations of Computer Science, IEEE, Palo Alto, CA, Nov. 1993."},{"key":"R19","unstructured":"C. K. Poon,\n                      A Sublinear Space, Polynomial Time Algorithm for Directed ST\u2010Connectivity on the JAG Model\n                      , Ph.D. thesis, University of Toronto, 1995."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80031-5"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0211010"},{"key":"R24","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"},{"key":"R25","unstructured":"R. Impagliazzo, personal communication, 1993."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795294402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:12Z","timestamp":1787335932000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795294402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795294402"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795294402","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}