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.ESA.2022.60
URN: urn:nbn:de:0030-drops-169988
Go to the corresponding LIPIcs Volume Portal

Georgiadis, Loukas ; Italiano, Giuseppe F. ; Kosinas, Evangelos

Computing the 4-Edge-Connected Components of a Graph: An Experimental Study

LIPIcs-ESA-2022-60.pdf (1 MB)


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

  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 =		{},
  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
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022
Supplementary Material: Software (Source Code): archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI