{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T12:41:01Z","timestamp":1774528861998,"version":"3.50.1"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319130743","type":"print"},{"value":"9783319130750","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_44","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"553-564","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Depth-First Search Using $$O(n)$$ Bits"],"prefix":"10.1007","author":[{"given":"Tetsuo","family":"Asano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taisuke","family":"Izumi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masashi","family":"Kiyomi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matsuo","family":"Konagaya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hirotaka","family":"Ono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Tarui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryuhei","family":"Uehara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"issue":"1","key":"44_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02122548","volume":"8","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Anderson, R.: A Random NC Algorithm for Depth-First Search. Combinatorica 8(1), 1\u201312 (1988)","journal-title":"Combinatorica"},{"issue":"2","key":"44_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(87)90105-0","volume":"24","author":"R Anderson","year":"1987","unstructured":"Anderson, R., Mayr, E.: Parallelism and the Maximal Path Problem. Information Processing Letters 24(2), 121\u2013126 (1987)","journal-title":"Information Processing Letters"},{"key":"44_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-642-38236-9_4","volume-title":"Theory and Applications of Models of Computation","author":"T Asano","year":"2013","unstructured":"Asano, T., Elmasry, A., Katajainen, J.: Priority Queues and Sorting for Read-Only Data. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 32\u201341. Springer, Heidelberg (2013)"},{"key":"44_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-40104-6_6","volume-title":"Algorithms and Data Structures","author":"T Asano","year":"2013","unstructured":"Asano, T., Kirkpatrick, D.: Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 61\u201372. Springer, Heidelberg (2013)"},{"key":"#cr-split#-44_CR5.1","doi-asserted-by":"crossref","unstructured":"Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O.: $$\\tilde{O}(\\sqrt{n})$$-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem. ECCC Report 71 (2014)","DOI":"10.1007\/978-3-662-44465-8_5"},{"key":"#cr-split#-44_CR5.2","unstructured":"also. In: \u00c9sik, Z., Csuhaj-Varj\u00fa, E., Dietzfelbinger, M. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 45-56. Springer, Heidelberg (2014)"},{"issue":"5","key":"44_CR6","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1137\/S0097539793283151","volume":"27","author":"G Barnes","year":"1998","unstructured":"Barnes, G., Buss, J., Ruzzo, W., Schieber, B.: A Sublinear Space, Polynomial Time Algorithm for Directed $$s$$-$$t$$ Connectivity. SIAM Journal of Computing 27(5), 1273\u20131282 (1998)","journal-title":"SIAM Journal of Computing"},{"key":"44_CR7","doi-asserted-by":"crossref","unstructured":"Elberfeld, M. Jakoby, A., Tantau, T.: Logspace Versions of the Theorems of Bodlaender and Courcelle. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 143\u2013152 (2010)","DOI":"10.1109\/FOCS.2010.21"},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Kawarabayashi, K.: Embedding and Canonizing Graphs of Bounded Genus in Logspace. In: Proceedings of the 46th Annual ACM Symposium on the Theory of Computing (STOC 2014), pp. 383\u2013392 (2014)","DOI":"10.1145\/2591796.2591865"},{"key":"44_CR9","unstructured":"Imai, T.: Polynomial-Time Memory Constrained Shortest Path Algorithms for Directed Graphs. In: Proceedings of the 12th Forum on Information Technology, vol. 1, pp. 9\u201316 (2013) (in Japanese)"},{"key":"44_CR10","doi-asserted-by":"crossref","unstructured":"Imai, T., Nakagawa, K., Pavan, A., Vinodchandran, N., Watanabe, O.: An $$O(n^{1\/2+\\epsilon })$$-Space and Polynomial-Time Algorithm for Directed Planar Reachability. In: Proceedings of 2013 IEEE Conference on Computational Complexity, pp. 277\u2013286 (2013)","DOI":"10.1109\/CCC.2013.35"},{"key":"44_CR11","doi-asserted-by":"crossref","unstructured":"Konagaya, M., Asano, T.: Reporting All Segment Intersections Using an Arbitrary Sized Work Space. IEICE Transactions 96-A(6), 1066\u20131071 (2013)","DOI":"10.1587\/transfun.E96.A.1066"},{"key":"44_CR12","unstructured":"Papadimitriou, C.: Computational complexity. Addison-Wesley (1994)"},{"issue":"5","key":"44_CR13","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J Reif","year":"1985","unstructured":"Reif, J.: Depth-First Search Is Inherently Sequential. Information Processing Letters 20(5), 229\u2013234 (1985)","journal-title":"Information Processing Letters"},{"key":"44_CR14","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected Connectivity in Log-Space. Journal of the ACM 55(4), 17:1\u201317:24 (2008)","DOI":"10.1145\/1391289.1391291"},{"issue":"2","key":"44_CR15","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing 1(2), 146\u2013160 (1972)","journal-title":"SIAM Journal on Computing"},{"key":"44_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1995.1025","volume":"19","author":"P de la Tore","year":"1995","unstructured":"de la Tore, P., Kruskal, C.: Fast Parallel Algorithms for Lexicographic Search and Path-Algebra Problems. Journal of Algorithms 19, 1\u201324 (1995)","journal-title":"Journal of Algorithms"},{"key":"44_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00224-001-1008-4","volume":"34","author":"P de la Tore","year":"2001","unstructured":"de la Tore, P., Kruskal, C.: Polynomially Improved Efficiency for Fast Parallel Single-Source Lexicographic Depth-First Search, Breadth-First Search, and Topological-First Search. Theory of Computing Systems 34, 275\u2013298 (2001)","journal-title":"Theory of Computing Systems"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T03:40:21Z","timestamp":1676000421000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}