{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:40:58Z","timestamp":1771026058993,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540309352","type":"print"},{"value":"9783540324263","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_77","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"767-776","source":"Crossref","is-referenced-by-count":8,"title":["Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs"],"prefix":"10.1007","author":[{"given":"Pinyan","family":"Lu","sequence":"first","affiliation":[]},{"given":"Jialin","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Chung Keung","family":"Poon","sequence":"additional","affiliation":[]},{"given":"Jin-Yi","family":"Cai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"77_CR1","first-page":"218","volume-title":"20th Annual Symposium on Foundations of Computer Science","author":"R. Aleliunas","year":"1979","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1979, pp. 218\u2013223. IEEE, Los Alamitos (1979)"},{"issue":"2","key":"77_CR2","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/rsa.3240050203","volume":"5","author":"N. Alon","year":"1994","unstructured":"Alon, N., Roichman, Y.: Random Cayley graphs and and expanders. Random Structures and Algorithms\u00a05(2), 271\u2013284 (1994)","journal-title":"Random Structures and Algorithms"},{"issue":"2","key":"77_CR3","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1145\/333979.333984","volume":"47","author":"R. Armoni","year":"2000","unstructured":"Armoni, R., Ta-Shma, A., Wigderson, A., Zhou, S.: An O(log(n)4\/3) space algorithm for (s,t) connectivity in undirected graphs. Journal of the ACM\u00a047(2), 294\u2013311 (2000)","journal-title":"Journal of the ACM"},{"issue":"5","key":"77_CR4","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1137\/S0097539793283151","volume":"27","author":"G. Barnes","year":"1998","unstructured":"Barnes, G., Buss, J.F., Ruzzo, W.L., Schieber, B.: A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM Journal on Computing\u00a027(5), 1273\u20131282 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"77_CR5","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1109\/SFCS.1983.31","volume-title":"24th Annual Symposium on Foundations of Computer Science","author":"P. Berman","year":"1983","unstructured":"Berman, P., Simon, J.: Lower bounds on graph threading by probabilistic machines. In: 24th Annual Symposium on Foundations of Computer Science, Tucson, AZ, November 1983, pp. 304\u2013311. IEEE, Los Alamitos (1983)"},{"issue":"3","key":"77_CR6","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1137\/0209048","volume":"9","author":"S.A. Cook","year":"1980","unstructured":"Cook, S.A., Rackoff, C.W.: Space lower bounds for maze threadability on restricted machines. SIAM Journal on Computing\u00a09(3), 636\u2013652 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"77_CR7","unstructured":"Dinur, I., Reingold, O., Trevisan, L., Vadhan, S.: Finding paths in nonreversible markov chains. Technical Report TR05-022, Electronic Colloquium on Computational Complexity (2005)"},{"issue":"6","key":"77_CR8","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1137\/S0097539795295948","volume":"28","author":"J. Edmonds","year":"1999","unstructured":"Edmonds, J., Poon, C.K., Achlioptas, D.: Tight lower bounds for st-connectivity on the NNJAG model. SIAM Journal on Computing\u00a028(6), 2257\u20132284 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"77_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-24597-1_18","volume-title":"FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science","author":"P. Gopalan","year":"2003","unstructured":"Gopalan, P., Lipton, R., Mehta, A.: Randomized time-space tradeoffs for directed graph connectivity. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol.\u00a02914, pp. 208\u2013216. Springer, Heidelberg (2003)"},{"issue":"5","key":"77_CR10","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM Journal on Computing\u00a017(5), 935\u2013938 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"77_CR11","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","volume":"19","author":"H.R. Lewis","year":"1982","unstructured":"Lewis, H.R., Papadimitriou, C.H.: Symmetric space-bounded computation. Theoretical Computer Science\u00a019(2), 161\u2013187 (1982)","journal-title":"Theoretical Computer Science"},{"key":"77_CR12","doi-asserted-by":"crossref","unstructured":"Lu, P., Zhang, J., Poon, C.K., Cai, J.: Simulating undirected st-oonnectivity algorithms on uniform JAGs and NNJAGs. Technical report (2005)","DOI":"10.1007\/11602613_77"},{"key":"77_CR13","doi-asserted-by":"crossref","unstructured":"Nisan, N.: ${\\it RL} \\subseteq {\\it SC}$ . In: Proceedings of the Twenty Fourth Annual ACM Symposium on Theory of Computing, Victoria, B.C., Canada, May 1992, pp. 619\u2013623 (1992)","DOI":"10.1145\/129712.129772"},{"key":"77_CR14","volume-title":"33rd Annual Symposium on Foundations of Computer Science","author":"N. Nisan","year":"1992","unstructured":"Nisan, N., Szemer\u00e9di, E., Wigderson, A.: Undirected connectivity in O(log1.5 n) space. In: 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, October 1992. IEEE, Los Alamitos (1992)"},{"key":"77_CR15","unstructured":"Poon, C.K.: On the Complexity of the ST-Connectivity Problem. PhD thesis, University of Toronto (1996)"},{"issue":"1-2","key":"77_CR16","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0304-3975(00)00019-0","volume":"237","author":"C.K. Poon","year":"2000","unstructured":"Poon, C.K.: A space lower bound for st-connectivity on node-named JAGs. Theoretical Computer Science\u00a0237(1-2), 327\u2013345 (2000)","journal-title":"Theoretical Computer Science"},{"key":"77_CR17","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: Proceedings of the Thirty Seventh Annual ACM Symposium on Theory of Computing, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"key":"77_CR18","doi-asserted-by":"crossref","unstructured":"Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics\u00a0155(1) (2001)","DOI":"10.2307\/3062153"},{"issue":"2","key":"77_CR19","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences\u00a04(2), 177\u2013192 (1970)","journal-title":"Journal of Computer and System Sciences"},{"key":"77_CR20","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"Szelepcs\u00e9nyi, R.: The method of forcing for nondeterministic automata. Bulletin of the European Association for Theoretical Computer Science\u00a033, 96\u2013100 (1987)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_77.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T03:05:28Z","timestamp":1736132728000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11602613_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}