Determining 4-edge-connected components in linear time

2021/05/04 by Nadara, Wojciech, Radecki, Mateusz, Smulewicz, Marcin +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2105.01699

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 by

• Deterministic Almost-Linear-Time Gomory-Hu Trees

Related

• Computing the 4-Edge-Connected Components of a Graph in Linear Time
• Improved Linear-Time Algorithm for Computing the 4-Edge-Connected Components of a Graph
• Computing the 5-Edge-Connected Components in Linear Time
• On finding 2-cuts and 3-edge-connected components in parallel
• A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs