Improved Linear-Time Algorithm for Computing the 4-Edge-Connected Components of a Graph

2021/08/19 by Georgiadis, Loukas, Italiano, Giuseppe F., Kosinas, Evangelos
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2108.08558

Abstract

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 it is simple to describe and to implement in the pointer machine model of computation.

Related

• Computing the 4-Edge-Connected Components of a Graph in Linear Time
• Determining 4-edge-connected components in linear time
• Computing the 5-Edge-Connected Components in Linear Time
• A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs
• Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More