An Improved Algorithm for Incremental DFS Tree in Undirected Graphs

Authors Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.16.pdf
  • Filesize: 0.73 MB
  • 12 pages

Document Identifiers

Author Details

Lijie Chen
  • Massachusetts Institute of Technology
Ran Duan
  • Tsinghua University
Ruosong Wang
  • Carnegie Mellon University
Hanrui Zhang
  • Duke University
Tianyi Zhang
  • Tsinghua University

Cite AsGet BibTex

Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, and Tianyi Zhang. An Improved Algorithm for Incremental DFS Tree in Undirected Graphs. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.16

Abstract

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].

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • DFS tree
  • fractional cascading
  • fully dynamic algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic dfs in undirected graphs: breaking the O(m) barrier. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 730-739. SIAM, 2016. Google Scholar
  2. Surender Baswana and Keerti Choudhary. On dynamic DFS tree in directed graphs. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 102-114. Springer, 2015. Google Scholar
  3. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O (log n) update time. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 383-392. IEEE, 2011. Google Scholar
  4. Surender Baswana and Shahbaz Khan. Incremental algorithm for maintaining DFS tree for undirected graphs. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 138-149. Springer, 2014. Google Scholar
  5. Michael A Bender and Martin Farach-Colton. The lca problem revisited. In Latin American Symposium on Theoretical Informatics, pages 88-94. Springer, 2000. Google Scholar
  6. Bernard Chazelle and Leonidas J Guibas. Fractional cascading: I. a data structuring technique. Algorithmica, 1(1-4):133-162, 1986. Google Scholar
  7. Bernard Chazelle and Leonidas J Guibas. Fractional cascading: II. applications. Algorithmica, 1(1-4):163-191, 1986. Google Scholar
  8. Camil Demetrescu and Giuseppe F Italiano. A new approach to dynamic all pairs shortest paths. Journal of the ACM (JACM), 51(6):968-992, 2004. Google Scholar
  9. Ran Duan and Tianyi Zhang. Improved distance sensitivity oracles via tree partitioning. arXiv preprint arXiv:1605.04491, 2016. Google Scholar
  10. David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig. Sparsification—a technique for speeding up dynamic graph algorithms. Journal of the ACM (JACM), 44(5):669-696, 1997. Google Scholar
  11. Paolo G Franciosa, Giorgio Gambosi, and Umberto Nanni. The incremental maintenance of a depth-first-search tree in directed acyclic graphs. Information processing letters, 61(2):113-120, 1997. Google Scholar
  12. Monika R Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM (JACM), 46(4):502-516, 1999. Google Scholar
  13. Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 48(4):723-760, 2001. Google Scholar
  14. Bruce M Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1131-1142. Society for Industrial and Applied Mathematics, 2013. Google Scholar
  15. Kengo Nakamura and Kunihiko Sadakane. A space-efficient algorithm for the dynamic dfs problem in undirected graphs. In International Workshop on Algorithms and Computation, pages 295-307. Springer, 2017. Google Scholar
  16. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12(1):7, 2016. Google Scholar
  17. Yakov Nekrich and Gonzalo Navarro. Sorted range reporting. In Scandinavian Workshop on Algorithm Theory (SWAT), pages 271-282. Springer, 2012. Google Scholar
  18. Liam Roditty and Uri Zwick. Improved dynamic reachability algorithms for directed graphs. SIAM Journal on Computing, 37(5):1455-1471, 2008. Google Scholar
  19. Liam Roditty and Uri Zwick. Dynamic approximate all-pairs shortest paths in undirected graphs. SIAM Journal on Computing, 41(3):670-683, 2012. Google Scholar
  20. Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse. In Foundations of Computer Science (FOCS), 2004. Proceedings. 45th Annual IEEE Symposium on, pages 509-517. IEEE, 2004. Google Scholar
  21. Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146-160, 1972. Google Scholar
  22. Mikkel Thorup. Fully-dynamic min-cut. In Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC), pages 224-230. ACM, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail