{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:33:11Z","timestamp":1760239991783,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T00:00:00Z","timestamp":1551225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Depth-first search (DFS) is a well-known graph traversal algorithm and can be performed in     O ( n + m )     time for a graph with n vertices and m edges. We consider the dynamic DFS problem, that is, to maintain a DFS tree of an undirected graph G under the condition that edges and vertices are gradually inserted into or deleted from G. We present an algorithm for this problem, which takes worst-case     O (   m n   \u00b7 polylog  ( n )  )     time per update and requires only     ( 3 m + o ( m ) ) log n     bits of space. This algorithm reduces the space usage of dynamic DFS algorithm to only 1.5 times as much space as that of the adjacency list of the graph. We also show applications of our dynamic DFS algorithm to dynamic connectivity, biconnectivity, and 2-edge-connectivity problems under vertex insertions and deletions.<\/jats:p>","DOI":"10.3390\/a12030052","type":"journal-article","created":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T11:41:03Z","timestamp":1551267663000},"page":"52","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Space-Efficient Fully Dynamic DFS in Undirected Graphs \u2020"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9615-3479","authenticated-orcid":false,"given":"Kengo","family":"Nakamura","sequence":"first","affiliation":[{"name":"Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8212-3682","authenticated-orcid":false,"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[{"name":"Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0020-0190(96)00202-5","article-title":"The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs","volume":"61","author":"Franciosa","year":"1997","journal-title":"Inf. Process. Lett."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Baswana, S., and Choudhary, K. (2015, January 24\u201328). On dynamic DFS tree in directed graphs. Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS), Milan, Italy.","DOI":"10.1007\/978-3-662-48054-0_9"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Baswana, S., and Khan, S. (2014, January 8\u201311). Incremental algorithm for maintaining DFS tree for undirected graphs. Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Copenhagen, Denmark.","DOI":"10.1007\/978-3-662-43948-7_12"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Baswana, S., Chaudhury, S.R., Choudhary, K., and Khan, S. (2016, January 10\u201312). Dynamic DFS in undirected graphs: Breaking the O(m) barrier. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, USA.","DOI":"10.1137\/1.9781611974331.ch52"},{"key":"ref_5","unstructured":"Chen, L., Duan, R., Wang, R., and Zhang, H. (arXiv, 2016). Improved algorithms for maintaining DFS tree in undirected graphs, arXiv."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Baswana, S., Chaudhury, S.R., Choudhary, K., and Khan, S. (arXiv, 2015). Dynamic DFS in undirected graphs: Breaking the O(m) barrier, arXiv.","DOI":"10.1137\/1.9781611974331.ch52"},{"key":"ref_7","unstructured":"Chen, L., Duan, R., Wang, R., Zhang, H., and Zhang, T. (2018, January 18\u201320). An improved algorithm for incremental DFS tree in undirected graphs. Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Malm\u00f6, Sweden."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Baswana, S., Goel, A., and Khan, S. (2018, January 7\u201310). Incremental DFS algorithms: A theoretical and experimental study. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, USA.","DOI":"10.1137\/1.9781611975031.4"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Khan, S. (2017, January 24\u201326). Near optimal parallel algorithms for dynamic DFS in undirected graphs. Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Washington, DC, USA.","DOI":"10.1145\/3087556.3087576"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Nakamura, K., and Sadakane, K. (2017, January 29\u201331). A space-efficient algorithm for the dynamic DFS problem in undirected graphs. Proceedings of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM), Hsinchu, Taiwan.","DOI":"10.1007\/978-3-319-53925-6_23"},{"key":"ref_11","unstructured":"Baswana, S., Gupta, S.K., and Tulsyan, A. (arXiv, 2018). Fault tolerant and fully dynamic DFS in undirected graphs: Simple yet efficient, arXiv."},{"key":"ref_12","unstructured":"Grossi, R., Gupta, A., and Vitter, J.S. (2003, January 12\u201314). High-order entropy-compressed text indexes. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, MD, USA."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/s004530010032","article-title":"Dynamically switching vertices in planar graphs","volume":"28","author":"Frigioni","year":"2000","journal-title":"Algorithmica"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1137\/090751670","article-title":"Dynamic connectivity: Connecting to networks and geometry","volume":"40","author":"Chan","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_15","unstructured":"Jacobson, G. (November, January 30). Space-efficient static trees and graphs. Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, NC, USA."},{"key":"ref_16","unstructured":"Clark, D. (1996). Compact Pat Trees. [Ph.D. Thesis, University of Waterloo]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","article-title":"Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets","volume":"3","author":"Raman","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.tcs.2015.11.011","article-title":"Fast construction of wavelet trees","volume":"638","author":"Munro","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","article-title":"A data structure for dynamic trees","volume":"26","author":"Sleator","year":"1983","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bender, M.A., and Farach-Colton, M. (2000, January 10\u201314). The LCA problem revisited. Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN), Punta del Esk, Uruguay.","DOI":"10.1007\/10719839_9"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., and Puglisi, S.J. (2016, January 10\u201312). Range predecessor and Lempel-Ziv parsing. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, USA.","DOI":"10.1137\/1.9781611974331.ch143"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.comgeo.2010.09.001","article-title":"Improved data structures for the orthogonal range successor problem","volume":"44","author":"Yu","year":"2011","journal-title":"Comput. Geom."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","article-title":"Wavelet trees for all","volume":"25","author":"Navarro","year":"2014","journal-title":"J. Discret. Algorithms"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Kreft, S., and Navarro, G. (2011, January 27\u201329). Self-indexing based on LZ77. Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM), Palermo, Italy.","DOI":"10.1007\/978-3-642-21458-5_6"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/3\/52\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:35:12Z","timestamp":1760186112000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/3\/52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,27]]},"references-count":24,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,3]]}},"alternative-id":["a12030052"],"URL":"https:\/\/doi.org\/10.3390\/a12030052","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,2,27]]}}}