Skip to Main content Skip to Navigation
New interface
Conference papers

Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice

Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Friday, October 22, 2021 - 2:18:52 PM
Last modification on : Tuesday, May 17, 2022 - 2:50:02 PM
Long-term archiving on: : Sunday, January 23, 2022 - 8:07:11 PM


Publisher files allowed on an open archive




Loukas Georgiadis, Konstantinos Giannis, Giuseppe F Italiano, Evangelos Kosinas. Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice. SEA 2021 - 19th International Symposium on Experimental Algorithms, Jun 2021, Nice, France. pp.1-19, ⟨10.4230/LIPIcs.SEA.2021.20⟩. ⟨hal-03395500⟩



Record views


Files downloads