2026-07-21T23:53:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8842 2024-03-06T10:42:46Z ddc:004 open_access

An Improved Algorithm for Incremental DFS Tree in Undirected Graphs Chen, Lijie Duan, Ran Wang, Ruosong Zhang, Hanrui Zhang, Tianyi DFS tree fractional cascading fully dynamic algorithm Depth first search (DFS) tree is one of the most well-known data structures for designing efficient graph algorithms. Given an undirected graph G=(V,E) with n vertices and m edges, the textbook algorithm takes O(n+m) time to construct a DFS tree. In this paper, we study the problem of maintaining a DFS tree when the graph is undergoing incremental updates. Formally, we show: Given an arbitrary online sequence of edge or vertex insertions, there is an algorithm that reports a DFS tree in O(n) worst case time per operation, and requires O (min {m log n, n^2}) preprocessing time. Our result improves the previous O(n log^3 n) worst case update time algorithm by Baswana et al. [Baswana et al., 2016] and the O(n log n) time by Nakamura and Sadakane [Nakamura and Sadakane, 2017], and matches the trivial Omega(n) lower bound when it is required to explicitly output a DFS tree. Our result builds on the framework introduced in the breakthrough work by Baswana et al. [Baswana et al., 2016], together with a novel use of a tree-partition lemma by Duan and Zhang [Duan and Zhang, 2016], and the celebrated fractional cascading technique by Chazelle and Guibas [Chazelle and Guibas, 1986a; Chazelle and Guibas, 1986b]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lijie Chen and Ran Duan and Ruosong Wang and Hanrui Zhang and Tianyi Zhang 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.16 urn:nbn:de:0030-drops-88427 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.16 eng https://creativecommons.org/licenses/by/3.0/legalcode