{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:38Z","timestamp":1725861518476},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_10","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T15:50:21Z","timestamp":1468943421000},"page":"119-130","source":"Crossref","is-referenced-by-count":10,"title":["Improved Space Efficient Algorithms for BFS, DFS and Applications"],"prefix":"10.1007","author":[{"given":"Niranka","family":"Banerjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sankardeep","family":"Chakraborty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"10_CR1","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)"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1007\/978-3-319-13075-0_44","volume-title":"Algorithms and Computation","author":"T Asano","year":"2014","unstructured":"Asano, T., et al.: Depth-first search using O(n) bits. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 553\u2013564. Springer, Heidelberg (2014)"},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-3-662-44465-8_5","volume-title":"Mathematical Foundations of Computer Science 2014","author":"T Asano","year":"2014","unstructured":"Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O.: $$\\widetilde{O}(\\sqrt{n})$$ -space and polynomial-time algorithm for planar directed graph reachability. In: \u00c9sik, Z., Csuhaj-Varj\u00fa, E., Dietzfelbinger, M. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 45\u201356. Springer, Heidelberg (2014)"},{"issue":"1","key":"10_CR4","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":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/978-3-319-21398-9_28","volume-title":"Computing and Combinatorics","author":"N Banerjee","year":"2015","unstructured":"Banerjee, N., Chakraborty, S., Raman, V., Roy, S., Saurabh, S.: Time-space tradeoffs for dynamic programming algorithms in trees and bounded treewidth graphs. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 349\u2013360. Springer, Heidelberg (2015)"},{"issue":"4","key":"10_CR6","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":"10_CR7","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":"10_CR8","unstructured":"Batagelj, V., Zaversnik, M.: An $${\\rm O}(m)$$ algorithm for cores decomposition of networks. CoRR cs.DS\/0310049 (2003)"},{"key":"10_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-45749-6_25","volume-title":"Algorithms - ESA 2002","author":"U Brandes","year":"2002","unstructured":"Brandes, U.: Eager $$st$$ -ordering. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 247\u2013256. Springer, Heidelberg (2002)"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-48447-7_4","volume-title":"Algorithms and Data Structures","author":"A Brodnik","year":"1999","unstructured":"Brodnik, A., Carlsson, S., Demaine, E.D., Munro, J.I., Sedgewick, R.D.: Resizable arrays in optimal time and space. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol. 1663, pp. 37\u201348. Springer, Heidelberg (1999)"},{"key":"10_CR11","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":"10_CR12","unstructured":"Clark, D.: Compact pat trees. Ph.D. thesis, University of Waterloo, Canada (1996)"},{"key":"10_CR13","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":"3"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/978-3-662-44777-2_24","volume-title":"Algorithms - ESA 2014","author":"O Darwish","year":"2014","unstructured":"Darwish, O., Elmasry, A.: Optimal time-space tradeoff for the 2D convex-hull problem. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 284\u2013295. Springer, Heidelberg (2014)"},{"key":"10_CR15","unstructured":"Elmasry, A., Hagerup, T., Kammer, F.: Space-efficient basic graph algorithms. In: 32nd STACS, pp. 288\u2013301 (2015)"},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2543629","volume":"18","author":"D Eppstein","year":"2013","unstructured":"Eppstein, D., Loffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithmics 18, 1\u20133 (2013)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"1","key":"10_CR17","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."},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/978-3-540-73420-8_46","volume-title":"Automata, Languages and Programming","author":"A Gupta","year":"2007","unstructured":"Gupta, A., Hon, W.-K., Shah, R., Vitter, J.S.: A framework for dynamizing succinct data structures. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 521\u2013532. Springer, Heidelberg (2007)"},{"key":"10_CR19","unstructured":"Hagerup, T., Kammer, F.: Succinct choice dictionaries. CoRR abs\/1604.06058 (2016)"},{"issue":"39","key":"10_CR20","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":"10_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"JI Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol. 1180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"10_CR22","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":"10_CR23","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."},{"issue":"4","key":"10_CR24","doi-asserted-by":"crossref","first-page":"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), 1\u201317 (2008)","journal-title":"J. ACM"},{"issue":"7","key":"10_CR25","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."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,24]],"date-time":"2020-09-24T03:41:09Z","timestamp":1600918869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}