Document Open Access Logo

2-Connectivity in Directed Graphs (Invited Talk)

Authors Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.1.pdf
  • Filesize: 1.4 MB
  • 14 pages

Document Identifiers

Author Details

Loukas Georgiadis
Giuseppe F. Italiano
Nikos Parotsidis

Cite As Get BibTex

Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. 2-Connectivity in Directed Graphs (Invited Talk). In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.1

Abstract

We survey some recent results on 2-edge and 2-vertex connectivity problems in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-vertex and 2-edge connectivity have a much richer and more complicated structure. It is thus not surprising that 2-connectivity problems on directed graphs appear to be more difficult than on undirected graphs. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth-first search. In the case of digraphs, however, the very same problems have been much more challenging and required the development of new tools and techniques.

Subject Classification

Keywords
  • 2-edge and 2-vertex connectivity on directed graphs
  • graph algorithms
  • dominator trees

Metrics

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

References

  1. 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
  2. J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications (Springer Monographs in Mathematics). Springer, 1st ed. 2001. 3rd printing edition, 2002. Google Scholar
  3. A. A. Benczúr. Counterexamples for directed and node capacitated cut-trees. SIAM J. Comput., 24:505-510, 1995. Google Scholar
  4. 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
  5. K. Chatterjee and M. Henzinger. Efficient and dynamic algorithms for alternating büchi games and maximal end-component decomposition. J. ACM, 61(3):15:1-15:40, 2014. URL: http://dx.doi.org/10.1145/2597631.
  6. J. Cheriyan and R. Thurimella. Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput., 30(2):528-560, 2000. Google Scholar
  7. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001. Google Scholar
  8. W. Di Luigi, L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-connectivity in directed graphs: An experimental study. In Proc. 17th Workshop on Algorithm Engineering and Experiments, pages 173-187, 2015. URL: http://dx.doi.org/10.1137/1.9781611973754.15.
  9. Ya. M. Erusalimskii and G. G. Svetlov. Bijoin points, bibridges, and biblocks of directed graphs. Cybernetics, 16(1):41-44, 1980. URL: http://dx.doi.org/10.1007/BF01099359.
  10. D. Firmani, G. F. Italiano, L. Laura, A. Orlandi, and F. Santaroni. Computing strong articulation points and strong bridges in large scale graphs. In Proc. 10th Int'l. Symp. on Experimental Algorithms, pages 195-207, 2012. Google Scholar
  11. 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.
  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. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979. Google Scholar
  14. L. Georgiadis. Approximating the smallest 2-vertex connected spanning subgraph of a directed graph. In Proc. 19th European Symposium on Algorithms, pages 13-24, 2011. Google Scholar
  15. L. Georgiadis, G. F. Italiano, A. Karanasiou, C. Papadopoulos, and N. Parotsidis. Sparse subgraphs for 2-connectivity in directed graphs. In Proc. 15th Int'l. Symp. on Experimental Algorithms, pages 150-166, 2016. URL: http://dx.doi.org/10.1007/978-3-319-38851-9_11.
  16. 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
  17. 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
  18. L. Georgiadis, G. F. Italiano, C. Papadopoulos, and N. Parotsidis. Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs. In ESA 2015, pages 582-594, 2015. Google Scholar
  19. L. Georgiadis, G. F. Italiano, and N. Parotsidis. Incremental 2-edge connectivity in directed graphs. In Proc. 43rd Int'l. Coll. on Automata, Languages, and Programming, 2016. To appear. Google Scholar
  20. L. Georgiadis, L. Laura, N. Parotsidis, and R. E. Tarjan. Loop nesting forests, dominators, and applications. In Proc. 13th Int'l. Symp. on Experimental Algorithms, pages 174-186, 2014. Google Scholar
  21. Y. Guo, F. Kuipers, and P. Van Mieghem. Link-disjoint paths for reliable QoS routing. International Journal of Communication Systems, 16(9):779-798, 2003. URL: http://dx.doi.org/10.1002/dac.612.
  22. M. Henzinger, V. King, and T. J. Warnow. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica, 24(1):1-13, 1999. URL: http://dx.doi.org/10.1007/PL00009268.
  23. M. Henzinger, S. Krinninger, and V. Loitzenbauer. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In Proc. 42nd Int'l. Coll. on Automata, Languages, and Programming, pages 713-724, 2015. Google Scholar
  24. A. Itai and M. Rodeh. The multi-tree approach to reliability in distributed networks. Information and Computation, 79(1):43-59, 1988. Google Scholar
  25. G. F. Italiano. Amortized efficiency of a path retrieval data structure. Theor. Comput. Sci., 48(3):273-281, 1986. URL: http://dx.doi.org/10.1016/0304-3975(86)90098-8.
  26. 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.
  27. 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.
  28. 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.
  29. B. Laekhanukit, S. O. Gharan, and M. Singh. A rounding by sampling approach to the minimum size k-arc connected subgraph problem. In ICALP 2012, pages 606-616, 2012. Google Scholar
  30. T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1(1):121-41, 1979. Google Scholar
  31. K. Menger. Zur allgemeinen kurventheorie. Fund. Math., 10:96-115, 1927. Google Scholar
  32. H. Nagamochi and T. Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, 2008. 1st edition. Google Scholar
  33. 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
  34. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  35. R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215-225, 1975. Google Scholar
  36. J. Westbrook and R. E. Tarjan. Maintaining bridge-connected and biconnected components on-line. Algorithmica, 7(5&6):433-464, 1992. URL: http://dx.doi.org/10.1007/BF01758773.
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