2020/02/11 by Yung H. Tsin, Tsin, Yung H.
Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2002.04727
openalex publication_date 2020/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A linear-time certifying algorithm for 3-edge-connectivity is presented. Given an undirected graph G, if G is 3-edge-connected, the algorithm generates a construction sequence as a positive certificate for G. Otherwise, the algorithm decomposes G into its 3-edge-connected components and at the same time generates a construction sequence for each connected component as well as the bridges and a cactus representation of the cut-pairs in G. All of these are done by making only one pass over G using an innovative graph contraction technique. Moreover, the graph need not be 2-edge-connected.