Determining 4-Edge-Connected Components in Linear Time

DOI10.4230/LIPICS.ESA.2021.71MaRDI QIDQ6075967zbMATH OpenOpenAlexFDO

Authors Wojciech Nadara, Marcin Smulewicz, Marek Sokołowski

Publication date 20 September 2023

Full work available at URL https://arxiv.org/abs/2105.01699

zbMATH Keywords

connectivitycutsgraphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-edge-cuts in a given 3-edge-connected graph, and then we use the output of this algorithm in order to determine the 4-edge-connected components of the graph.

Cited in

(8)

• Maintaining the classes of 4-edge-connectivity in a graph on-line
• A linear-time algorithm for four-partitioning four-connected planar graphs
• scientific article; zbMATH DE number 7740902 (Why is no real title available?)
• Computing the 4-edge-connected components of a graph: an experimental study
• On maximal k-edge-connected subgraphs of undirected graphs
• Higher connectivity in directed graphs (invited talk)
• Faster dynamic 2-edge connectivity in directed graphs
• A linear-delay algorithm for enumerating strongly-connected induced subgraphs based on SSD set system

This page was built for publication: Determining 4-Edge-Connected Components in Linear Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075967)