Document Open Access Logo

Incremental 2-Edge-Connectivity in Directed Graphs

Authors Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.49.pdf
  • Filesize: 1.14 MB
  • 15 pages

Document Identifiers

Author Details

Loukas Georgiadis
Giuseppe F. Italiano
Nikos Parotsidis

Cite As Get BibTex

Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. Incremental 2-Edge-Connectivity in Directed Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.49

Abstract

We present an algorithm that can update the 2-edge-connected blocks of a directed graph with n vertices through a sequence of m edge insertions in a total of O(m*n) time. After each insertion, we can answer the following queries in asymptotically optimal time:

- Test in constant time if two query vertices v and w are 2-edge-connected. Moreover, if v and w are not 2-edge-connected, we can produce in constant time a “witness” of this property, by exhibiting an edge that is contained in all paths from v to w or in all paths from w to v.

- Report in O(n) time all the 2-edge-connected blocks of G.

This is the first dynamic algorithm for 2-connectivity problems on directed graphs, and it matches the best known bounds for simpler problems, such as incremental transitive closure.

Subject Classification

Keywords
  • 2-edge connectivity on directed graphs; dynamic graph algorithms; incremental algorithms.

Metrics

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

References

  1. A. Abboud and V. Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th IEEE Symp. on Foundations of Computer Science, FOCS, pages 434-443, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.53.
  2. S. Alstrup, D. Harel, P. W. Lauridsen, and M. Thorup. Dominators in linear time. SIAM Journal on Computing, 28(6):2117-32, 1999. Google Scholar
  3. S. Alstrup and P. W. Lauridsen. A simple dynamic algorithm for maintaining a dominator tree. Technical Report 96-3, Department of Computer Science, University of Copenhagen, 1996. Google Scholar
  4. M. A. Bender, J. T. Fineman, S. Gilbert, and R. E. Tarjan. A new approach to incremental cycle detection and related problems. ACM Transactions on Algorithms, 12(2):14:1-14:22, December 2015. URL: http://dx.doi.org/10.1145/2756553.
  5. A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook. Linear-time algorithms for dominators and other path-evaluation problems. SIAM Journal on Computing, 38(4):1533-1573, 2008. Google Scholar
  6. C. Demetrescu and G. F. Italiano. A new approach to dynamic all pairs shortest paths. Journal of ACM, 51(6):968-992, 2004. URL: http://dx.doi.org/10.1145/1039488.1039492.
  7. C. Demetrescu and G. F. Italiano. Mantaining dynamic matrices for fully dynamic transitive closure. Algorithmica, 51(4):387-427, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9051-4.
  8. D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification - A technique for speeding up dynamic graph algorithms. Journal of ACM, 44(5):669-696, September 1997. URL: http://dx.doi.org/10.1145/265910.265914.
  9. W. Fraczak, L. Georgiadis, A. Miller, and R. E. Tarjan. Finding dominators via disjoint set union. Journal of Discrete Algorithms, 23:2-20, 2013. URL: http://dx.doi.org/10.1016/j.jda.2013.10.003.
  10. P. G. Franciosa, G. Gambosi, and U. Nanni. The incremental maintenance of a depth-first-search tree in directed acyclic graphs. Information Processing Letters, 61(2):113-120, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(96)00202-5.
  11. G. N. Frederickson. Data structures for on-line updating of minimum spanning trees. SIAM Journal on Computing, 14:781-798, 1985. Google Scholar
  12. H. N. Gabow. The minset-poset approach to representations of graph connectivity. ACM Transactions on Algorithms, 12(2):24:1-24:73, February 2016. URL: http://dx.doi.org/10.1145/2764909.
  13. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-edge connectivity in directed graphs. In Proc. 26th ACM-SIAM Symp. on Discrete Algorithms, pages 1988-2005, 2015. Google Scholar
  14. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-vertex connectivity in directed graphs. In Proc. 42nd Int'l. Coll. on Automata, Languages, and Programming, pages 605-616, 2015. Google Scholar
  15. L. Georgiadis, G. F. Italiano, L. Laura, and F. Santaroni. An experimental study of dynamic dominators. In Proc. 20th European Symp. on Algorithms, pages 491-502, 2012. Google Scholar
  16. L. Georgiadis, G. F. Italiano, and N. Parotsidis. A New Framework for Strong Connectivity and 2-Connectivity in Directed Graphs. ArXiv e-prints, abs/1511.02913, November 2015. URL: http://arxiv.org/abs/1511.02913.
  17. B. Haeupler, T. Kavitha, R. Mathew, S. Sen, and R. E. Tarjan. Incremental cycle detection, topological ordering, and strong component maintenance. ACM Transactions on Algorithms, 8(1):3:1-3:33, January 2012. URL: http://dx.doi.org/10.1145/2071379.2071382.
  18. M. Henzinger, S. Krinninger, and V. Loitzenbauer. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), 2015. Google Scholar
  19. M. R. Henzinger and V. King. Fully dynamic biconnectivity and transitive closure. In Proc. 36th IEEE Symp. on Foundations of Computer Science, pages 664-672, 1995. URL: http://dx.doi.org/10.1109/SFCS.1995.492668.
  20. M. R. Henzinger and V. King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of ACM, 46(4):502-536, 1999. Google Scholar
  21. M. R. Henzinger and V. King. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing, 31(2):364-374, February 2002. URL: http://dx.doi.org/10.1137/S0097539797327209.
  22. J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of ACM, 48(4):723-760, July 2001. URL: http://dx.doi.org/10.1145/502090.502095.
  23. G. F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(3):273-281, 1986. URL: http://dx.doi.org/10.1016/0304-3975(86)90098-8.
  24. G. F. Italiano, L. Laura, and F. Santaroni. Finding strong bridges and strong articulation points in linear time. Theoretical Computer Science, 447:74-84, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2011.11.011.
  25. R. Jaberi. Computing the 2-blocks of directed graphs. RAIRO-Theor. Inf. Appl., 49(2):93-119, 2015. URL: http://dx.doi.org/10.1051/ita/2015001.
  26. R. Jaberi. On computing the 2-vertex-connected components of directed graphs. Discrete Applied Mathematics, 204:164-172, 2016. URL: http://dx.doi.org/10.1016/j.dam.2015.10.001.
  27. V. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proc. 40th IEEE Symp. on Foundations of Computer Science, FOCS'99, pages 81-91, 1999. URL: http://dx.doi.org/10.1109/SFFCS.1999.814580.
  28. S. Makino. An algorithm for finding all the k-components of a digraph. International Journal of Computer Mathematics, 24(3-4):213-221, 1988. Google Scholar
  29. A. Marchetti-Spaccamela, U. Nanni, and H. Rohnert. Maintaining a topological order under edge insertions. Information Processing Letters, 59(1):53-58, 1996. URL: http://dx.doi.org/10.1016/0020-0190(96)00075-0.
  30. H. Nagamochi and T. Watanabe. Computing k-edge-connected components of a multigraph. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E76-A.4:513-517, 1993. Google Scholar
  31. M. Pătraşcu and M. Thorup. Planning for fast connectivity updates. In Proc. 48th IEEE Symp. on Foundations of Computer Science, FOCS'07, pages 263-271, 2007. URL: http://dx.doi.org/10.1109/FOCS.2007.54.
  32. G. Ramalingam and T. Reps. An incremental algorithm for maintaining the dominator tree of a reducible flowgraph. In Proc. of the 21st ACM SIGPLAN-SIGACT Symp. on Principles of programming languages, pages 287-296, 1994. Google Scholar
  33. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  34. R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of ACM, 22(2):215-225, 1975. Google Scholar
  35. R. E. Tarjan. Edge-disjoint spanning trees and depth-first search. Acta Informatica, 6(2):171-85, 1976. Google Scholar
  36. R. E. Tarjan and J. van Leeuwen. Worst-case analysis of set union algorithms. Journal of ACM, 31(2):245-81, 1984. Google Scholar
  37. M. Thorup. Near-optimal fully-dynamic graph connectivity. In Proc. 32nd ACM Symp. on Theory of Computing, STOC'00, pages 343-350, 2000. URL: http://dx.doi.org/10.1145/335305.335345.
  38. M. Thorup. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory,, pages 384-396, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27810-8_33.
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