2026-07-23T19:28:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16998 2024-03-06T10:58:55Z ddc:004 open_access

Computing the 4-Edge-Connected Components of a Graph: An Experimental Study Georgiadis, Loukas Italiano, Giuseppe F. Kosinas, Evangelos Connectivity Cuts Edge Connectivity Graph Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loukas Georgiadis and Giuseppe F. Italiano and Evangelos Kosinas 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.60 urn:nbn:de:0030-drops-169988 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.60 eng https://creativecommons.org/licenses/by/4.0/legalcode