Document Open Access Logo

Computing the 4-Edge-Connected Components of a Graph: An Experimental Study

Authors Loukas Georgiadis , Giuseppe F. Italiano , Evangelos Kosinas

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.60.pdf
  • Filesize: 1.46 MB
  • 16 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

  • Georgiadis, Loukas: 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.
  • Italiano, Giuseppe F.: Partially supported by MIUR, the Italian Ministry for Education, University and Research, under PRIN Project AHeAD (Efficient Algorithms for HArnessing Networked Data).
  • Kosinas, Evangelos: Supported by the project "Dioni: Computing Infrastructure for Big-Data Processing and Analysis". (MIS No. 5047222) which is implemented under the Action "Reinforcement of the Research and Innovation Infrastructure", funded by the Operational Programme "Competitiveness, Entrepreneurship and Innovation" (NSRF 2014-2020) and co-financed by Greece and the European Union (European Regional Development Fund).

Cite AsGet BibTex

Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing the 4-Edge-Connected Components of a Graph: An Experimental Study. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.60

Abstract

The notions of edge-cuts and k-edge-connected components are fundamental in graph theory with numerous practical applications. Very recently, the first linear-time algorithms for computing all the 3-edge cuts and the 4-edge-connected components of a graph have been introduced. In this paper we present carefully engineered implementations of these algorithms and evaluate their efficiency in practice, by performing a thorough empirical study using both real-world graphs taken from a variety of application areas, as well as artificial graphs. To the best of our knowledge, this is the first experimental study for these problems, which highlights the merits and weaknesses of each technique. Furthermore, we present an improved algorithm for computing the 4-edge-connected components of an undirected graph in linear time. The new algorithm uses only elementary data structures, and is implementable in the pointer machine model of computation.

Subject Classification

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

Metrics

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

Related Versions

Supplementary Materials

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), pages 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, pages 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. K. P. Eswaran and R. E. Tarjan. Augmentation problems. SIAM Journal on Computing, 5(4):653-665, 1976. URL: https://doi.org/10.1137/0205044.
  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. Z. Galil and G. F. Italiano. Reducing edge connectivity to vertex connectivity. SIGACT News, 22(1):57-61, March 1991. URL: https://doi.org/10.1145/122413.122416.
  7. L. Georgiadis, K. Giannis, G. F. Italiano, and E. Kosinas. Computing vertex-edge cut-pairs and 2-edge cuts in practice. In David Coudert and Emanuele Natale, editors, 19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France, volume 190 of LIPIcs, pages 20:1-20:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.SEA.2021.20.
  8. L. Georgiadis, G. F. Italiano, and E. Kosinas. Computing the 4-edge-connected components of a graph in linear time. In Proc. 29th European Symposium on Algorithms, 2021. Full version available at https://arxiv.org/abs/2105.02910. Google Scholar
  9. L. Georgiadis, G. F. Italiano, and E. Kosinas. Improved linear-time algorithm for computing the 4-edge-connected components of a graph, 2021. URL: https://doi.org/10.48550/ARXIV.2108.08558.
  10. 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.
  11. D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-55, 1984. 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. 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.
  14. 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.
  15. 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, pages 246-255, USA, 2009. Society for Industrial and Applied Mathematics. Google Scholar
  16. J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
  17. K. Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10(1):96-115, 1927. Google Scholar
  18. W. Nadara, M. Radecki, M. Smulewicz, and M. Sokołowski. Determining 4-edge-connected components in linear time. In Proc. 29th European Symposium on Algorithms, 2021. Full version available at https://arxiv.org/abs/2105.01699. Google Scholar
  19. 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.
  20. H. Nagamochi and T. Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, 2008. 1st edition. Google Scholar
  21. 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
  22. D. Naor, D. Gusfield, and C. Martel. A fast algorithm for optimally increasing the edge connectivity. SIAM Journal on Computing, 26(4):1139-1165, 1997. Google Scholar
  23. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  24. R. E. Tarjan. Finding dominators in directed graphs. SIAM Journal on Computing, 3(1):62-89, 1974. Google Scholar
  25. R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215-225, 1975. Google Scholar
  26. 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/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