2023/06/25 by Yung H. Tsin, Tsin, Yung H.
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Model-Driven Software Engineering Techniques #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2306.14103
openalex publication_date 2023/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a connected undirected multigraph G (a graph that may contain parallel edges), the algorithm of [19] finds the 3-edge-connected components of G in linear time using an innovative graph contraction technique based on a depth-first search. In [21], it was shown that the algorithm can be extended to produce a Mader construction sequence for each 3-edge-connected component, a cactus representation of the 2-cuts (cut-pairs) of each 2-edge-connected component of G, and the 1-cuts (bridges) at the same time. In this paper, we further extend the algorithm of [19] to generate the 2-cuts and the 3-edge-connected components of G simultaneously in linear time by performing only one depth-first search over the input graph. Previously known algorithms solve the two problems separately in multiple phases.