Document Open Access Logo

Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

Authors Surender Baswana, Shiv Gupta, Ayush Tulsyan

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.65.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Surender Baswana
  • Department of Computer Science & Engineering, IIT Kanpur, Kanpur, India
Shiv Gupta
  • Department of Computer Science & Engineering, IIT Kanpur, Kanpur, India
Ayush Tulsyan
  • Department of Computer Science & Engineering, IIT Kanpur, Kanpur, India

Funding

  • Baswana, Surender: This research work was partly done during a visit to University of Paderborn supported by a fellowship from the Alexander von Humboldt Foundation.

Cite As Get BibTex

Surender Baswana, Shiv Gupta, and Ayush Tulsyan. Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.65

Abstract

We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithms for this problem, uses optimal space and optimal preprocessing time, and still achieves better time complexity. This algorithm also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Depth first search
  • DFS
  • Dynamic graph algorithms
  • Fault tolerant

Metrics

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

Related Versions

References

  1. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On Fully Dynamic Graph Sparsifiers. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 335-344, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.44.
  2. Alok Aggarwal, Richard J. Anderson, and Ming-Yang Kao. Parallel Depth-First Search in General Directed Graphs. SIAM J. Comput., 19(2):397-409, 1990. URL: http://dx.doi.org/10.1137/0219025.
  3. Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic DFS in Undirected Graphs: breaking the O(m) barrier. In Symposium on Discrete Algorithms, SODA, pages 730-739, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch52.
  4. Surender Baswana and Keerti Choudhary. On Dynamic DFS Tree in Directed Graphs. In MFCS, Proceedings, Part II, pages 102-114, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48054-0_9.
  5. Surender Baswana, Ayush Goel, and Shahbaz Khan. Incremental DFS algorithms: a theoretical and experimental study. In Symposium on Discrete Algorithms, SODA, pages 53-72, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.4.
  6. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully Dynamic Maximal Matching in O(log n) Update Time (Corrected Version). SIAM J. Comput., 47(3):617-650, 2018. URL: http://dx.doi.org/10.1137/16M1106158.
  7. Surender Baswana and Shahbaz Khan. Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs. In ICALP, Proceedings, Part I, pages 138-149, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_12.
  8. Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms, 8(4):35:1-35:51, 2012. URL: http://dx.doi.org/10.1145/2344422.2344425.
  9. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. SIAM J. Comput., 47(3):859-887, 2018. URL: http://dx.doi.org/10.1137/140998925.
  10. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS, pages 18:1-18:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.18.
  11. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Fault-Tolerant Approximate Shortest-Path Trees. Algorithmica, 80(12):3437-3460, 2018. URL: http://dx.doi.org/10.1007/s00453-017-0396-z.
  12. Gilad Braunschvig, Shiri Chechik, David Peleg, and Adam Sealfon. Fault tolerant additive and (μ, α)-spanners. Theor. Comput. Sci., 580:94-100, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.02.036.
  13. Timothy M. Chan, Mihai Patrascu, and Liam Roditty. Dynamic Connectivity: Connecting to Networks and Geometry. In Symposium on Foundations of Computer Science, FOCS, pages 95-104, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.29.
  14. Bernard Chazelle and Leonidas J. Guibas. Fractional Cascading: I. A Data Structuring Technique. Algorithmica, 1(2):133-162, 1986. URL: http://dx.doi.org/10.1007/BF01840440.
  15. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault Tolerant Spanners for General Graphs. SIAM J. Comput., 39(7):3403-3423, 2010. URL: http://dx.doi.org/10.1137/090758039.
  16. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-Sensitivity Distance Oracles and Routing Schemes. Algorithmica, 63(4):861-882, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9543-0.
  17. Lijie Chen, Ran Duan, Ruosong Wang, and Hanrui Zhang. Improved Algorithms for Maintaining DFS Tree in Undirected Graphs. CoRR, abs/1607.04913, 2016. URL: http://arxiv.org/abs/1607.04913v2,
  18. Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, and Tianyi Zhang. An Improved Algorithm for Incremental DFS Tree in Undirected Graphs. In SWAT, pages 16:1-16:12, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2018.16.
  19. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM, 51(6):968-992, 2004. URL: http://dx.doi.org/10.1145/1039488.1039492.
  20. Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for Distances Avoiding a Failed Node or Link. SIAM J. Comput., 37(5):1299-1318, 2008. URL: http://dx.doi.org/10.1137/S0097539705429847.
  21. Ran Duan. New Data Structures for Subgraph Connectivity. In ICALP, Proceedings, Part I, pages 201-212, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_18.
  22. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669-696, 1997. URL: http://dx.doi.org/10.1145/265910.265914.
  23. Shimon Even and Yossi Shiloach. An On-Line Edge-Deletion Problem. J. ACM, 28(1):1-4, 1981. URL: http://dx.doi.org/10.1145/322234.322235.
  24. Paolo Giulio Franciosa, Giorgio Gambosi, and Umberto Nanni. The Incremental Maintenance of a Depth-First-Search Tree in Directed Acyclic Graphs. Inf. Process. Lett., 61(2):113-120, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(96)00202-5.
  25. Daniele Frigioni and Giuseppe F. Italiano. Dynamically Switching Vertices in Planar Graphs. Algorithmica, 28(1):76-103, 2000. URL: http://dx.doi.org/10.1007/s004530010032.
  26. Lee-Ad Gottlieb and Liam Roditty. Improved algorithms for fully dynamic geometric spanners and geometric routing. In Symposium on Discrete Algorithms, SODA, pages 591-600, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347148.
  27. Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text indexes. In Symposium on Discrete Algorithms, SODA, pages 841-850, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644250.
  28. Manoj Gupta and Shahbaz Khan. Multiple Source Dual Fault Tolerant BFS Trees. In 44th International Colloquium on Automata, Languages, and Programming, ICALP, pages 127:1-127:15, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.127.
  29. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. J. ACM, 65(6):36:1-36:40, 2018. URL: https://dl.acm.org/citation.cfm?id=3218657, URL: http://dx.doi.org/10.1145/3218657.
  30. Monika Rauch Henzinger and Valerie King. Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation. J. ACM, 46(4):502-516, 1999. URL: http://dx.doi.org/10.1145/320211.320215.
  31. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. URL: http://dx.doi.org/10.1145/502090.502095.
  32. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Symposium on Discrete Algorithms, SODA, pages 1131-1142, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.81.
  33. Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, and Roberto Tamassia. Complexity Models for Incremental Computation. Theor. Comput. Sci., 130(1):203-236, 1994. URL: http://dx.doi.org/10.1016/0304-3975(94)90159-7.
  34. Kengo Nakamura and Kunihiko Sadakane. A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs. In In International Workshop on Algorithms and Computation, pages 295-307, 2017. URL: http://dx.doi.org/10.1007/978-3-319-53925-6_23.
  35. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 950-961, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.92.
  36. John H. Reif. Depth-First Search is Inherently Sequential. Inf. Process. Lett., 20(5):229-234, 1985. URL: http://dx.doi.org/10.1016/0020-0190(85)90024-9.
  37. John H. Reif. A Topological Approach to Dynamic Graph Connectivity. Inf. Process. Lett., 25(1):65-70, 1987. URL: http://dx.doi.org/10.1016/0020-0190(87)90095-0.
  38. Liam Roditty. Fully Dynamic Geometric Spanners. Algorithmica, 62(3-4):1073-1087, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9504-7.
  39. Liam Roditty and Uri Zwick. Improved Dynamic Reachability Algorithms for Directed Graphs. SIAM J. Comput., 37(5):1455-1471, 2008. URL: http://dx.doi.org/10.1137/060650271.
  40. Liam Roditty and Uri Zwick. Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. SIAM J. Comput., 41(3):670-683, 2012. URL: http://dx.doi.org/10.1137/090776573.
  41. Piotr Sankowski. Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). In Symposium on Foundations of Computer Science, FOCS, pages 509-517, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.25.
  42. Daniel Dominic Sleator and Robert Endre Tarjan. A Data Structure for Dynamic Trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90006-5.
  43. Shay Solomon. Fully Dynamic Maximal Matching in Constant Update Time. In Symposium on Foundations of Computer Science, FOCS, pages 325-334, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.43.
  44. Robert Endre Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput., 1(2):146-160, 1972. URL: http://dx.doi.org/10.1137/0201010.
  45. Mikkel Thorup. Fully-Dynamic Min-Cut. Combinatorica, 27(1):91-127, 2007. URL: http://dx.doi.org/10.1007/s00493-007-0045-2.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact