Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.60
URN: urn:nbn:de:0030-drops-169988
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16998/
Georgiadis, Loukas ; Italiano, Giuseppe F. ; Kosinas, Evangelos
Computing the 4-Edge-Connected Components of a Graph: An Experimental Study
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{georgiadis_et_al:LIPIcs.ESA.2022.60,
author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Kosinas, Evangelos},
title = {{Computing the 4-Edge-Connected Components of a Graph: An Experimental Study}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {60:1--60:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16998},
URN = {urn:nbn:de:0030-drops-169988},
doi = {10.4230/LIPIcs.ESA.2022.60},
annote = {Keywords: Connectivity Cuts, Edge Connectivity, Graph Algorithms}
}
| Keywords: | Connectivity Cuts, Edge Connectivity, Graph Algorithms | |
| Seminar: | 30th Annual European Symposium on Algorithms (ESA 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 01.09.2022 | |
| Supplementary Material: | Software (Source Code): https://github.com/4eComponentsALGO/files archived at: https://archive.softwareheritage.org/swh:1:dir:f82f28576eba10039b91356977e84253d67c73a3 |
