{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T15:56:26Z","timestamp":1773330986003,"version":"3.50.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,1,22]],"date-time":"2018-01-22T00:00:00Z","timestamp":1516579200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00224-017-9841-2","type":"journal-article","created":{"date-parts":[[2018,1,21]],"date-time":"2018-01-21T22:57:21Z","timestamp":1516575441000},"page":"1736-1762","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Space Efficient Linear Time Algorithms for BFS, DFS and Applications"],"prefix":"10.1007","volume":"62","author":[{"given":"Niranka","family":"Banerjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0719-160X","authenticated-orcid":false,"given":"Sankardeep","family":"Chakraborty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,22]]},"reference":[{"key":"9841_CR1","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Addison-Wesley, Boston (1974)"},{"key":"9841_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity - a modern approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational complexity - a modern approach. Cambridge University Press, Cambridge (2009)"},{"issue":"3","key":"9841_CR3","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1016\/j.comgeo.2013.11.004","volume":"47","author":"T Asano","year":"2014","unstructured":"Asano, T., Buchin, K., Buchin, M., Korman, M., Mulzer, W., Rote, G., Schulz, A.: Reprint of: Memory-constrained algorithms for simple polygons. Comput. Geom. 47(3), 469\u2013479 (2014)","journal-title":"Comput. Geom."},{"key":"9841_CR4","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: 25th ISAAC, LNCS, vol. 8889, pp 553\u2013564 (2014)","DOI":"10.1007\/978-3-319-13075-0_44"},{"key":"9841_CR5","doi-asserted-by":"crossref","unstructured":"Asano, T., Kirkpatrick, D.G., Nakagawa, K., Watanabe, O.: O\u0307(\u221a n)-space and polynomial-time algorithm for planar directed graph reachability. In: 39th MFCS LNCS, vol. 8634, pp 45\u201356 (2014)","DOI":"10.1007\/978-3-662-44465-8_5"},{"issue":"1","key":"9841_CR6","first-page":"46","volume":"2","author":"T Asano","year":"2011","unstructured":"Asano, T., Mulzer, W., Rote, G., Wang, Y.: Constant-work-space algorithms for geometric problems. JoCG 2(1), 46\u201368 (2011)","journal-title":"JoCG"},{"key":"9841_CR7","doi-asserted-by":"crossref","unstructured":"Banerjee, N., Chakraborty, S., Raman, V.: Improved space efficient algorithms for BFS, DFS and applications. In: 22nd COCOON, vol. 9797, pp 119\u2013130. Springer, LNCS (2016)","DOI":"10.1007\/978-3-319-42634-1_10"},{"key":"9841_CR8","doi-asserted-by":"crossref","unstructured":"Banerjee, N., Chakraborty, S., Raman, V., Roy, S., Saurabh, S.: Time-space tradeoffs for dynamic programming in trees and bounded treewidth graphs. In: 21st COCOON, vol. 9198, pp 349\u2013360. Springer, LNCS (2015)","DOI":"10.1007\/978-3-319-21398-9_28"},{"issue":"4","key":"9841_CR9","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1007\/s00453-014-9893-5","volume":"72","author":"L Barba","year":"2015","unstructured":"Barba, L., Korman, M., Langerman, S., Sadakane, K., Silveira, R.I.: Space-time trade-offs for stack-based algorithms. Algorithmica 72(4), 1097\u20131129 (2015)","journal-title":"Algorithmica"},{"issue":"5","key":"9841_CR10","doi-asserted-by":"crossref","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. SICOMP 27(5), 1273\u20131282 (1998)","journal-title":"SICOMP"},{"key":"9841_CR11","unstructured":"Batagelj, V., Zaversnik, M.: An O(m) algorithm for cores decomposition of networks. CoRR, arXiv:0310049 (2003)"},{"key":"9841_CR12","doi-asserted-by":"crossref","unstructured":"Brandes, U.: Eager st-ordering. In: ESA, pp 247\u2013256 (2002)","DOI":"10.1007\/3-540-45749-6_25"},{"issue":"4","key":"9841_CR13","first-page":"337","volume":"3","author":"GS Brodal","year":"1996","unstructured":"Brodal, G.S., Chaudhuri, S., Radhakrishnan, J.: The randomized complexity of maintaining the minimum. Nord. J. Comput. 3(4), 337\u2013351 (1996)","journal-title":"Nord. J. Comput."},{"key":"9841_CR14","doi-asserted-by":"crossref","unstructured":"Brodnik, A., Carlsson, S., Demaine, E.D., Munro, J.I., Sedgewick, R.: Resizable arrays in optimal time and space. In: 6th WADS, LNCS, vol. 1663, pp 37\u201348 (1999)","DOI":"10.1007\/3-540-48447-7_4"},{"issue":"2","key":"9841_CR15","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.comgeo.2005.11.005","volume":"34","author":"H Bro\u0307nnimann","year":"2006","unstructured":"Bro\u0307nnimann, H., Chan, T.M.: Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. Comput. Geom. 34(2), 75\u201382 (2006)","journal-title":"Comput. Geom."},{"key":"9841_CR16","unstructured":"Chakraborty, D., Pavan, A., Tewari, R., Vinodchandran, N.V., Yang, L.: New time-space upperbounds for directed reachability in high-genus and h-minor-free graphs. In: FSTTCS, pp 585\u2013595 (2014)"},{"key":"9841_CR17","unstructured":"Chakraborty, S., Jo, S., Satti, S.R.: Improved space-efficient linear time algorithms for some classical graph problems. In: 15th CTW (2017)"},{"key":"9841_CR18","unstructured":"Chakraborty, S., Raman, V., Satti, S.R.: Biconnectivity, chain decomposition and st-numbering using O(n) bits. In: 27th ISAAC, pp 22:1\u201322:13 (2016)"},{"key":"9841_CR19","doi-asserted-by":"crossref","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, st-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":"9841_CR20","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Satti, S.R.: Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications. In: 23rd COCOON, pp 87\u201398 (2017)","DOI":"10.1007\/978-3-319-62389-4_8"},{"key":"9841_CR21","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Munro, J.I., Raman, V.: Selection and sorting in the \u201drestore\u201d model. In: 25th SODA, pp 995\u20131004 (2014)","DOI":"10.1137\/1.9781611973402.74"},{"key":"9841_CR22","volume-title":"Compact pat trees","author":"D Clark","year":"1996","unstructured":"Clark, D.: Compact pat trees. PhD thesis. University of Waterloo, Canada (1996)"},{"key":"9841_CR23","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. MIT Press, Cambridge (2009)","edition":"3rd edn."},{"key":"9841_CR24","doi-asserted-by":"crossref","unstructured":"Darwish, O., Elmasry, A.: Optimal time-space tradeoff for the 2d convex-hull problem. In: 22nd ESA, pp 284\u2013295 (2014)","DOI":"10.1007\/978-3-662-44777-2_24"},{"key":"9841_CR25","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Patrascu, M., Thorup, M.: Changing base without losing space. In: 42nd STOC, pp 593\u2013602 (2010)","DOI":"10.1145\/1806689.1806771"},{"key":"9841_CR26","unstructured":"Ellen, F.: Constant time operations for words of length w. Unpublished Manuscript"},{"key":"9841_CR27","unstructured":"Elmasry, A., Hagerup, T., Kammer, F.: Space-efficient basic graph algorithms. In: 32nd STACS, pp 288\u2013301 (2015)"},{"key":"9841_CR28","doi-asserted-by":"crossref","unstructured":"Elmasry, A., Juhl, D.D., Katajainen, J., Satti, S.R.: Selection from read-only memory with limited workspace, vol. 554, pp 64\u201373 (2014)","DOI":"10.1016\/j.tcs.2014.06.012"},{"key":"9841_CR29","unstructured":"Elmasry, A., Kammer, F.: Space-efficient plane-sweep algorithms. In: 27th ISAAC, pp 30:1\u201330:13 (2016)"},{"key":"9841_CR30","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Loffler, M., Strash, D: Listing all maximal cliques in large sparse real-world graphs. ACM Journal of Experimental Algorithmics, 18 (2013)","DOI":"10.1145\/2543629"},{"issue":"1","key":"9841_CR31","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0022-0000(87)90002-X","volume":"34","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci. 34(1), 19\u201326 (1987)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9841_CR32","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1002\/spe.2314","volume":"46","author":"K Fredriksson","year":"2016","unstructured":"Fredriksson, K., Kilpela\u0307inen, P.: Practically efficient array initialization. Softw. Pract. Exper. 46(4), 435\u2013467 (2016)","journal-title":"Softw. Pract. Exper."},{"issue":"3-4","key":"9841_CR33","doi-asserted-by":"crossref","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-4), 107\u2013114 (2000)","journal-title":"Inf. Process. Lett."},{"key":"9841_CR34","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hon, W., Shah, R., Vitter, J.S.: A framework for dynamizing succinct data structures. In: 34th ICALP, pp 521\u2013532. Proceedings, Wroclaw (2007)","DOI":"10.1007\/978-3-540-73420-8_46"},{"key":"9841_CR35","unstructured":"Hagerup, T., Kammer, F.: Succinct choice dictionaries. CoRR, arXiv:1604.06058 (2016)"},{"issue":"39","key":"9841_CR36","doi-asserted-by":"crossref","first-page":"5176","DOI":"10.1016\/j.tcs.2011.05.023","volume":"412","author":"WK Hon","year":"2011","unstructured":"Hon, W.K., Sadakane, K., Sung, W.K.: Succinct data structures for searchable partial sums with optimal worst-case performance. Theor Comput. Sci. 412(39), 5176\u20135186 (2011)","journal-title":"Theor Comput. Sci."},{"key":"9841_CR37","unstructured":"Kammer, F., Kratsch, D., Laudahn, M.: Space-efficient biconnected components and recognition of outerplanar graphs. In: 41st MFCS, pp 56:1\u201356:14 (2016)"},{"key":"9841_CR38","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data structures and algorithms 1: sorting and searching, volume 1 of eatcs monographs on theoretical computer science","author":"K Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data structures and algorithms 1: sorting and searching, volume 1 of eatcs monographs on theoretical computer science. Springer, Berlin (1984)"},{"key":"9841_CR39","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pagh, R., Patrascu, M.: On dynamic range reporting in one dimension. In: 37th STOC, pp 104\u2013111 (2005)","DOI":"10.1145\/1060590.1060606"},{"key":"9841_CR40","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: FSTTCS LNCS, vol. 1180, pp 37\u201342 (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"9841_CR41","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.: Selection and sorting with limited storage. Theor. Comput. Sci. 12, 315\u2013323 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9841_CR42","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(95)00225-1","volume":"165","author":"JI Munro","year":"1996","unstructured":"Munro, J.I., Raman, V.: Selection from read-only memory and sorting with minimum data movement. Theor. Comput. Sci. 165(2), 311\u2013323 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"9841_CR43","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications. Found. Trends Theor. Comput. Sci. 1(2) (2005)","DOI":"10.1561\/0400000002"},{"key":"9841_CR44","doi-asserted-by":"crossref","unstructured":"Poyias, A., Puglisi, S.J., Raman, R.: Compact dynamic rewritable (cdrw) arrays To appear in 19th ALENEX (2017)","DOI":"10.1137\/1.9781611974768.9"},{"key":"9841_CR45","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct dynamic data structures. In: 7th WADS, LNCS 2125, pp 426\u2013437 (2001)","DOI":"10.1007\/3-540-44634-6_39"},{"issue":"4","key":"9841_CR46","doi-asserted-by":"crossref","first-page":"17:1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17:1\u201317:24 (2008)","journal-title":"J. ACM"},{"key":"9841_CR47","volume-title":"Structure and constructions of 3-connected graphs","author":"JM Schmidt","year":"2011","unstructured":"Schmidt, J.M.: Structure and constructions of 3-connected graphs. PhD thesis, Free University of Berlin, Berlin (2011)"},{"issue":"7","key":"9841_CR48","doi-asserted-by":"crossref","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":"9841_CR49","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9841_CR50","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/0020-0190(74)90003-9","volume":"2","author":"RE Tarjan","year":"1974","unstructured":"Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Process. Lett. 2 (6), 160\u2013161 (1974)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9841_CR51","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9841-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9841-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9841-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T12:39:48Z","timestamp":1570624788000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9841-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,22]]},"references-count":51,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["9841"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9841-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,22]]}}}