Document Open Access Logo

Computing the 4-Edge-Connected Components of a Graph in Linear Time

Authors Loukas Georgiadis , Giuseppe F. Italiano , Evangelos Kosinas

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.47.pdf
  • Filesize: 0.79 MB
  • 17 pages

Document Identifiers

Author Details

Loukas Georgiadis
  • Department of Computer Science & Engineering, University of Ioannina, Greece
Giuseppe F. Italiano
  • LUISS University, Rome, Italy
Evangelos Kosinas
  • Department of Computer Science & Engineering, University of Ioannina, Greece

Funding

Research at the University of Ioannina 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. G. F. Italiano is partially supported by MIUR, the Italian Ministry for Education, University and Research, under PRIN Project AHeAD (Efficient Algorithms for HArnessing Networked Data).

Cite AsGet BibTex

Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing the 4-Edge-Connected Components of a Graph in Linear Time. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.47

Abstract

We present the first linear-time algorithm that computes the 4-edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing 4-edge connectivity. Our results are based on a linear-time algorithm that computes the 3-edge cuts of a 3-edge-connected graph G, and a linear-time procedure that, given the collection of all 3-edge cuts, partitions the vertices of G into the 4-edge-connected components.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Cuts
  • Edge Connectivity
  • Graph Algorithms

Metrics

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

Related Versions

References

  1. E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov. On the structure of a family of minimal weighted cuts in a graph. Studies in Discrete Optimization (in Russian), page 290–306, 1976. Google Scholar
  2. Y. Dinitz. The 3-edge-components and a structural description of all 3-edge-cuts in a graph. In Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, WG '92, page 145–157, Berlin, Heidelberg, 1992. Springer-Verlag. Google Scholar
  3. Y. Dinitz and J. Westbrook. Maintaining the classes of 4-edge-connectivity in a graph on-line. Algorithmica, 20:242–276, 1998. URL: https://doi.org/10.1007/PL00009195.
  4. 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
  5. Z. Galil and G. F. Italiano. Reducing edge connectivity to vertex connectivity. SIGACT News, 22(1):57–61, 1991. URL: https://doi.org/10.1145/122413.122416.
  6. L. Georgiadis, G. F. Italiano, and E. Kosinas. Computing the 4-edge-connected components of a graph in linear time. CoRR, abs/2105.02910, 2021. URL: http://arxiv.org/abs/2105.02910.
  7. L. Georgiadis and E. Kosinas. Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation (ISAAC 2020), volume 181 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.38.
  8. M. Ghaffari, K. Nowicki, and M. Thorup. Faster algorithms for edge connectivity via random 2-out contractions. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, page 1260–1279, USA, 2020. Society for Industrial and Applied Mathematics. Google Scholar
  9. M. Henzinger, S. Rao, and D. Wang. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing, 49(1):1–36, 2020. Google Scholar
  10. J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing, 2(3):135-158, 1973. Google Scholar
  11. A. Kanevsky and V. Ramachandran. Improved algorithms for graph four-connectivity. Journal of Computer and System Sciences, 42(3):288-306, 1991. URL: https://doi.org/10.1016/0022-0000(91)90004-O.
  12. A. Kanevsky, R. Tamassia, G. Di Battista, and J. Chen. On-line maintenance of the four-connected components of a graph. In Proceedings 32nd Annual Symposium of Foundations of Computer Science (FOCS 1991), pages 793-801, 1991. URL: https://doi.org/10.1109/SFCS.1991.185451.
  13. D. R. Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46–76, January 2000. URL: https://doi.org/10.1145/331605.331608.
  14. D. R. Karger and D. Panigrahi. A near-linear time algorithm for constructing a cactus representation of minimum cuts. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, page 246–255, USA, 2009. Society for Industrial and Applied Mathematics. Google Scholar
  15. K.-I. Kawarabayashi and M. Thorup. Deterministic edge connectivity in near-linear time. Journal of the ACM, 66(1), December 2018. URL: https://doi.org/10.1145/3274663.
  16. K. Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10(1):96-115, 1927. Google Scholar
  17. W. Nadara, M. Radecki, M. Smulewicz, and M. Sokolowski. Determining 4-edge-connected components in linear time. In Proc. 29th European Symposium on Algorithms, 2021. Google Scholar
  18. H. Nagamochi and T. Ibaraki. A linear time algorithm for computing 3-edge-connected components in a multigraph. Japan J. Indust. Appl. Math, 9(163), 1992. URL: https://doi.org/10.1007/BF03167564.
  19. H. Nagamochi and T. Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, 2008. 1st edition. Google Scholar
  20. H. Nagamochi and T. Watanabe. Computing k-edge-connected components of a multigraph. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 76(4):513-517, 1993. Google Scholar
  21. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  22. R. E. Tarjan. Finding dominators in directed graphs. SIAM Journal on Computing, 3(1):62-89, 1974. Google Scholar
  23. R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215-225, 1975. Google Scholar
  24. R. E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of Computer and System Sciences, 18(2):110-27, 1979. Google Scholar
  25. 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