{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:23Z","timestamp":1787337503769,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We prove a time-space tradeoff for traversing undirected graphs, using a structured model that is a nonjumping variant of Cook and Rackoff's \"jumping automata for graphs.\"<\/jats:p>","DOI":"10.1137\/s0097539793282947","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1051-1072","source":"Crossref","is-referenced-by-count":6,"title":["A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata"],"prefix":"10.1137","volume":"28","author":[{"given":"Paul","family":"Beame","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Allan","family":"Borodin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prabhakar","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Walter L.","family":"Ruzzo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Tompa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"Leonard Adleman, Two theorems on random polynomial time, IEEE, Long Beach, Calif., 1978, 75\u20138380e:68095"},{"key":"R2","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"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90125-V"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0218018"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793283151"},{"key":"R6","unstructured":"G. Barnes and J. A. Edmonds,\n                      Time\u2010space lower bounds for directed s\u2010t connectivity on JAG models\n                      , in Proceedings 34th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 228\u2013237."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194264988"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202039"},{"key":"R9","unstructured":"Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter Ruzzo, Martin Tompa, Time\u2010space tradeoffs for undirected graph traversal, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 429\u20134381150712"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0085"},{"key":"R11","unstructured":"P. Berman and J. Simon,\n                      Lower bounds on graph threading by probabilistic machines\n                      , in 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson, AZ, 1983, pp. 304\u2013311."},{"key":"R12","unstructured":"Manuel Blum, Dexter Kozen, On the power of the compass (or, why mazes are easier to search than graphs), IEEE, Long Beach, Calif., 1978, 0\u20130, 132\u2013142,80f:68064"},{"key":"R13","unstructured":"Manuel Blum, William Sakoda, On the capability of finite automata in 2 and 3 dimensional space, IEEE Comput. Soc., Long Beach, Calif., 1977, 147\u201316158:32071"},{"key":"R14","first-page":"171","author":"Borodin A.","year":"1982","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0218038"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0218038"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90046-L"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90019-8"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790190144"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1117"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0209048"},{"key":"R21","unstructured":"J. A. Edmonds,\n                      Time\u2010space trade\u2010offs for undirected ST\u2010connectivity on a JAG\n                      , in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, 1993, pp. 718\u2013727."},{"key":"R22","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 Proceedings of the 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 147\u2013156."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1471"},{"key":"R24","unstructured":"A. Hemmerling,\n                      Labyrinth Problems: Labyrinth\u2010Searching Abilities of Automata\n                      , Teubner\u2010Texte Math. 114, Teubner, Leipzig, 1989."},{"key":"R25","unstructured":"S. Istrail,\n                      Polynomial universal traversing sequences for cycles are constructible\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, 1988, pp. 491\u2013503."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90197-4"},{"key":"R27","unstructured":"Logic and Algorithmic\n                      , An International Symposium Held in Honor of Ernst Specker, Z\u00fcrich, Feb. 5\u201311, 1980, Monographie No. 30 de L\u2019Enseignement Math\u00e9matique, Universit\u00e9 de Gen\u00e8ve, Switzerland, 1982."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205052"},{"key":"R29","unstructured":"N. Nisan, E. Szemer\u00e9di, and A. Wigderson,\n                      Undirected connectivity in O(log1.5n) space\n                      , in Proceedings 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 1992, pp. 24\u201329."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80031-5"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0211010"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0221067"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793282947","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:17Z","timestamp":1787336057000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793282947"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793282947"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793282947","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}