2026-07-25T02:57:37Z https://drops.dagstuhl.de/oai

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

Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice Georgiadis, Loukas Giannis, Konstantinos Italiano, Giuseppe F. Kosinas, Evangelos 2-Connectivity Graph Algorithms Split Components We consider two problems regarding the computation of connectivity cuts in undirected graphs, namely identifying vertex-edge cut-pairs and identifying 2-edge cuts, and present an experimental study of efficient algorithms for their computation. In the first problem, we are given a biconnected graph G and our goal is to find all vertices v such that G⧵v is not 2-edge-connected, while in the second problem, we are given a 2-edge-connected graph G and our goal is to find all edges e such that G⧵e is not 2-edge-connected. These problems are motivated by the notion of twinless strong connectivity in directed graphs but are also of independent interest. Moreover, the computation of 2-edge cuts is a main step in algorithms that compute the 3-edge-connected components of a graph. In this paper, we present streamlined versions of two recent linear-time algorithms of Georgiadis and Kosinas that compute all vertex-edge cut-pairs and all 2-edge cuts, respectively. We compare the empirical performance of our vertex-edge cut-pairs algorithm with an alternative linear-time method that exploits the structure of the triconnected components of G. Also, we compare the empirical performance of our 2-edge cuts algorithm with the algorithm of Tsin, which was reported to be the fastest one among the previously existing for this problem. To that end, we conduct a thorough experimental study to highlight the merits and weaknesses of each technique. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loukas Georgiadis and Konstantinos Giannis and Giuseppe F. Italiano and Evangelos Kosinas 2021 Is Part Of LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2021.20 urn:nbn:de:0030-drops-137920 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.20 eng https://creativecommons.org/licenses/by/4.0/legalcode