{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T11:16:34Z","timestamp":1725880594995},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319539249"},{"type":"electronic","value":"9783319539256"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-53925-6_23","type":"book-chapter","created":{"date-parts":[[2017,2,20]],"date-time":"2017-02-20T01:12:36Z","timestamp":1487553156000},"page":"295-307","source":"Crossref","is-referenced-by-count":2,"title":["A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs"],"prefix":"10.1007","author":[{"given":"Kengo","family":"Nakamura","sequence":"first","affiliation":[]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,21]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Baswana, S., Chaudhury, S.R., Choudhary, K., Khan, S.: Dynamic DFS in undirected graphs: breaking the $${O}(m)$$ barrier. In: Proceedings of SODA, pp. 730\u2013739 (2016)","DOI":"10.1137\/1.9781611974331.ch52"},{"key":"23_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-662-48054-0_9","volume-title":"Mathematical Foundations of Computer Science 2015","author":"S Baswana","year":"2015","unstructured":"Baswana, S., Choudhary, K.: On dynamic DFS tree in directed graphs. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 102\u2013114. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48054-0_9"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-662-43948-7_12","volume-title":"Automata, Languages, and Programming","author":"S Baswana","year":"2014","unstructured":"Baswana, S., Khan, S.: Incremental algorithm for maintaining DFS tree for undirected graphs. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 138\u2013149. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-43948-7_12"},{"key":"23_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). doi: 10.1007\/10719839_9"},{"key":"23_CR5","unstructured":"Chen, L., Duan, R., Wang, R., Zhang, H.: Improved algorithms for maintaining DFS tree in undirected graphs (2016). arXiv:1607.04913v2"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0020-0190(96)00202-5","volume":"61","author":"PG Franciosa","year":"1997","unstructured":"Franciosa, P.G., Gambosi, G., Nanni, U.: The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs. Inf. Process. Lett. 61, 113\u2013120 (1997)","journal-title":"Inf. Process. Lett."},{"key":"23_CR7","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of SODA, pp. 841\u2013850 (2003)"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-21458-5_6","volume-title":"Combinatorial Pattern Matching","author":"S Kreft","year":"2011","unstructured":"Kreft, S., Navarro, G.: Self-indexing based on LZ77. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 41\u201354. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-21458-5_6"},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.tcs.2015.11.011","volume":"638","author":"JI Munro","year":"2016","unstructured":"Munro, J.I., Nekrich, Y., Vitter, J.S.: Fast construction of wavelet trees. Theor. Comput. Sci. 638, 91\u201397 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR10","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","volume":"25","author":"G Navarro","year":"2014","unstructured":"Navarro, G.: Wavelet trees for all. J. Discrete Algorithms 25, 2\u201320 (2014)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"23_CR11","first-page":"16","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully-functional static and dynamic succinct trees. ACM TALG 10(3), 16 (2014)","journal-title":"ACM TALG"},{"issue":"4","key":"23_CR12","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding $$k$$ -ary trees, prefix sums and multisets. ACM TALG 3(4), 43 (2007)","journal-title":"ACM TALG"},{"key":"23_CR13","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53925-6_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T10:54:19Z","timestamp":1498388059000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53925-6_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319539249","9783319539256"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53925-6_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}