Document Open Access Logo

Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems

Authors Loukas Georgiadis , Evangelos Kosinas

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.38.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Author Details

Loukas Georgiadis
  • University of Ioannina, Greece
Evangelos Kosinas
  • University of Ioannina, Greece

Funding

Research supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the "First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant", Project FANTA (eFficient Algorithms for NeTwork Analysis), number HFRI-FM17-431.

Cite AsGet BibTex

Loukas Georgiadis and Evangelos Kosinas. Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.38

Abstract

A directed graph G = (V,E) is twinless strongly connected if it contains a strongly connected spanning subgraph without any pair of antiparallel (or twin) edges. The twinless strongly connected components (TSCCs) of a directed graph G are its maximal twinless strongly connected subgraphs. These concepts have several diverse applications, such as the design of telecommunication networks and the structural stability of buildings. A vertex v ∈ V is a twinless strong articulation point of G, if the deletion of v increases the number of TSCCs of G. Here, we present the first linear-time algorithm that finds all the twinless strong articulation points of a directed graph. We show that the computation of twinless strong articulation points reduces to the following problem in undirected graphs, which may be of independent interest: Given a 2-vertex-connected undirected graph H, find all vertices v for which there exists an edge e such that H⧵{v,e} is not connected. We develop a linear-time algorithm that not only finds all such vertices v, but also computes the number of edges e such that H⧵{v,e} is not connected. This also implies that for each twinless strong articulation point v which is not a strong articulation point in a strongly connected digraph G, we can compute the number of TSCCs in G⧵v.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • 2-connectivity
  • cut pairs
  • strongly connected components

Metrics

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

Related Versions

References

  1. G. Battista and R. Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, 15(4):302–318, April 1996. Google Scholar
  2. G. Battista and R. Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956–997, October 1996. Google Scholar
  3. S. Chechik, T. D. Hansen, G. F. Italiano, V. Loitzenbauer, and N. Parotsidis. Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs. In Proc. 28th ACM-SIAM Symp. on Discrete Algorithms, (SODA 2017), pages 1900-1918, 2017. Google Scholar
  4. D. Fussell, V. Ramachandran, and R. Thurimella. Finding triconnected components by local replacement. SIAM J. Comput., 22(3):587–616, June 1993. URL: https://doi.org/10.1137/0222040.
  5. H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30(2):209-21, 1985. Google Scholar
  6. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-edge connectivity in directed graphs. ACM Transactions on Algorithms, 13(1):9:1-9:24, 2016. Announced at SODA 2015. URL: https://doi.org/10.1145/2968448.
  7. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-vertex connectivity in directed graphs. Information and Computation, 261:248-264, 2018. ICALP 2015. URL: https://doi.org/10.1016/j.ic.2018.02.007.
  8. L. Georgiadis, G. F. Italiano, and N. Parotsidis. Strong connectivity in directed graphs under failures, with applications. In SODA, pages 1880-1899, 2017. Google Scholar
  9. L. Georgiadis and E. Kosinas. Linear-time algorithms for computing twinless strong articulation points and related problems. ArXiv, abs/2007.03933, 2020. URL: http://arxiv.org/abs/2007.03933.
  10. C. Gutwenger and P. Mutzel. A linear time implementation of spqr-trees. In Joe Marks, editor, Graph Drawing, pages 77-90, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. Google Scholar
  11. 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, (ICALP 2015), pages 713-724, 2015. Google Scholar
  12. J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing, 2(3):135-158, 1973. Google Scholar
  13. 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: https://doi.org/10.1016/j.tcs.2011.11.011.
  14. R. Jaberi. 2-edge-twinless blocks, 2019. URL: http://arxiv.org/abs/1912.13347.
  15. R. Jaberi. Computing 2-twinless blocks, 2019. URL: http://arxiv.org/abs/1912.12790.
  16. R. Jaberi. Twinless articulation points and some related problems, 2019. URL: http://arxiv.org/abs/1912.11799.
  17. S. Raghavan. Twinless strongly connected components. In F. B. Alt, M. C. Fu, and B. L. Golden, editors, Perspectives in Operations Research: Papers in Honor of Saul Gass' 80th Birthday, pages 285-304. Springer US, Boston, MA, 2006. URL: https://doi.org/10.1007/978-0-387-39934-8_17.
  18. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  19. R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215-225, 1975. Google Scholar
  20. Y. H. Tsin. Yet another optimal algorithm for 3-edge-connectivity. Journal of Discrete Algorithms, 7(1):130-146, 2009. Selected papers from the 1st International Workshop on Similarity Search and Applications (SISAP). URL: https://doi.org/10.1016/j.jda.2008.04.003.
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 Imprint Privacy Contact