A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs

2023/09/25 by Tsin, Yung H.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2309.13827

Abstract

A linear-time algorithm for generating auxiliary subgraphs for the 3-edge-connected components of a connected multigraph is presented. The algorithm uses an innovative graph contraction operation and makes only one pass over the graph. By contrast, the previously best-known algorithms make multiple passes over the graph to decompose it into its 2-edge-connected components or 2-vertex-connected components, then its 3-edge-connected components or 3-vertex-connected components, and then construct a cactus representation for the 2-cuts to generate the auxiliary subgraphs for the 3-edge-connected components.

Related

• On finding 2-cuts and 3-edge-connected components in parallel
• A simple certifying algorithm for 3-edge-connectivity
• Determining 4-edge-connected components in linear time
• 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