License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.20
URN: urn:nbn:de:0030-drops-137920
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13792/
Georgiadis, Loukas ;
Giannis, Konstantinos ;
Italiano, Giuseppe F. ;
Kosinas, Evangelos
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.
BibTeX - Entry
@InProceedings{georgiadis_et_al:LIPIcs.SEA.2021.20,
author = {Georgiadis, Loukas and Giannis, Konstantinos and Italiano, Giuseppe F. and Kosinas, Evangelos},
title = {{Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice}},
booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)},
pages = {20:1--20:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-185-6},
ISSN = {1868-8969},
year = {2021},
volume = {190},
editor = {Coudert, David and Natale, Emanuele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13792},
URN = {urn:nbn:de:0030-drops-137920},
doi = {10.4230/LIPIcs.SEA.2021.20},
annote = {Keywords: 2-Connectivity, Graph Algorithms, Split Components}
}
