{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T02:17:50Z","timestamp":1768443470313,"version":"3.49.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T00:00:00Z","timestamp":1569196800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T00:00:00Z","timestamp":1569196800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00453-019-00629-x","type":"journal-article","created":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T14:02:38Z","timestamp":1569247358000},"page":"1033-1056","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Space-Efficient DFS and Applications to Connectivity Problems: Simpler, Leaner, Faster"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6974-2473","authenticated-orcid":false,"given":"Torben","family":"Hagerup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,23]]},"reference":[{"key":"629_CR1","volume-title":"Data Structures and Algorithms","author":"AV Aho","year":"1983","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Data Structures and Algorithms. Addison-Wesley, Reading, Massachusetts (1983)"},{"key":"629_CR2","doi-asserted-by":"crossref","unstructured":"Asano, T., Izumi, T., Kiyomi, M., Konagaya M., Ono, H., Otachi, Y., Schweitzer, P., Tarui, J., Uehara, R.: Depth-first search using $$O(n)$$ bits. In: Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of LNCS, pp. 553\u2013564. Springer (2014)","DOI":"10.1007\/978-3-319-13075-0_44"},{"issue":"8","key":"629_CR3","doi-asserted-by":"publisher","first-page":"1736","DOI":"10.1007\/s00224-017-9841-2","volume":"62","author":"N Banerjee","year":"2018","unstructured":"Banerjee, N., Chakraborty, S., Raman, V., Satti, S.R.: Space efficient linear time algorithms for BFS, DFS and applications. Theory Comput. Syst. 62(8), 1736\u20131762 (2018)","journal-title":"Theory Comput. Syst."},{"key":"629_CR4","doi-asserted-by":"crossref","unstructured":"Baumann, T., Hagerup, T.: Rank-select indices without tears. In: Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2019), volume 11646 of LNCS, pp. 85\u201398. Springer (2019)","DOI":"10.1007\/978-3-030-24766-9_7"},{"key":"629_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.jcss.2017.06.006","volume":"90","author":"S Chakraborty","year":"2017","unstructured":"Chakraborty, S., Raman, V., Satti, S.R.: Biconnectivity, $$s t$$-numbering and other applications of DFS using $$O(n)$$ bits. J. Comput. Syst. Sci. 90, 63\u201379 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"629_CR6","unstructured":"Choudhari, J., Gupta, M., Sharma, S.: Nearly optimal space efficient algorithm for depth first search. Computing Research Repository (CoRR), \narXiv:1810.07259\n\n [cs.DS] (2018)"},{"key":"629_CR7","unstructured":"Clark, D.: Compact Pat Trees. Ph.D. thesis, University of Waterloo (1996)"},{"key":"629_CR8","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"key":"629_CR9","doi-asserted-by":"crossref","unstructured":"Dodis, Y., P\u01cetra\u015fcu, M., Thorup, M.: Changing base without losing space. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pp. 593\u2013602. ACM (2010)","DOI":"10.1145\/1806689.1806771"},{"key":"629_CR10","unstructured":"Elmasry, A., Hagerup, T., Kammer, F.: Space-efficient basic graph algorithms. In: Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume\u00a030 of LIPIcs, pp. 288\u2013301. Schloss Dagstuhl\u2013Leibniz\u2013Zentrum f\u00fcr Informatik (2015)"},{"issue":"3\u20134","key":"629_CR11","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(00)00051-X","volume":"74","author":"HN Gabow","year":"2000","unstructured":"Gabow, H.N.: Path-based depth-first search for strong and biconnected components. Inf. Process. Lett. 74(3\u20134), 107\u2013114 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"629_CR12","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. Theor. Comput. Sci. 387(3), 348\u2013359 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"629_CR13","unstructured":"Hagerup, T.: An optimal choice dictionary. Computing Research Repository (CoRR), \narXiv:1711.00808\n\n [cs.DS] (2017)"},{"key":"629_CR14","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Space-efficient DFS and applications: Simpler, leaner, faster. Computing Research Repository (CoRR), \narXiv:1805.11864\n\n [cs.DS] (2018)","DOI":"10.1007\/s00453-019-00629-x"},{"key":"629_CR15","unstructured":"Hagerup, T., Kammer, F.: Succinct choice dictionaries. Computing Research Repository (CoRR), \narXiv:1604.06058\n\n [cs.DS] (2016)"},{"key":"629_CR16","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.tcs.2018.01.008","volume":"754","author":"T Hagerup","year":"2019","unstructured":"Hagerup, T., Kammer, F., Laudahn, M.: Space-efficient Euler partition and bipartite edge coloring. Theor. Comput. Sci. 754, 16\u201334 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"629_CR17","unstructured":"Kammer, F., Kratsch, D., Laudahn, M.: Space-efficient biconnected components and recognition of outerplanar graphs. In: Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume\u00a058 of LIPIcs, pp. 56:1\u201356:14. Schloss Dagstuhl\u2013Leibniz\u2013Zentrum f\u00fcr Informatik (2016)"},{"key":"629_CR18","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding $$k$$-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43:1\u201343:25 (2007)","DOI":"10.1145\/1290672.1290680"},{"issue":"2","key":"629_CR19","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"7","key":"629_CR20","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.ipl.2013.01.016","volume":"113","author":"JM Schmidt","year":"2013","unstructured":"Schmidt, J.M.: A simple test on 2-vertex- and 2-edge-connectivity. Inf. Process. Lett. 113(7), 241\u2013244 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"629_CR21","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 J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"629_CR22","doi-asserted-by":"crossref","unstructured":"Vigna, S.: Broadword implementation of rank\/select queries. In: Proceedings of the 7th International Workshop on Experimental Algorithms (WEA 2008), volume 5038 of LNCS, pp. 154\u2013168. Springer (2008)","DOI":"10.1007\/978-3-540-68552-4_12"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00629-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00629-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00629-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T23:06:52Z","timestamp":1600729612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00629-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,23]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["629"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00629-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,23]]},"assertion":[{"value":"23 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}