title: A Simple Algorithm for Finding All k-Edge-Connected Components.
abstract: The problem of finding k-edge-connected components is a fundamental problem in computer science. Given a graph G = (V, E), the problem is to partition the vertex set V into {V1, V2,…, Vh}, where each Vi is maximized, such that for any two vertices x and y in Vi, there are k edge-disjoint paths connecting them. In this paper, we present an algorithm to solve this problem for all k. The algorithm preprocesses the input graph to construct an Auxiliary Graph to store information concerning edge-connectivity among every vertex pair in O(Fn) time, where F is the time complexity to find the maximum flow between two vertices in graph G and n = ∣V∣. For any value of k, the k-edge-connected components can then be determined by traversing the auxiliary graph in O(n) time. The input graph can be a directed or undirected, simple graph or multigraph. Previous works on this problem mainly focus on fixed value of k.
authors.affiliation: Software School, Fudan University, Shanghai, China.
authors.forename: Tianhao
authors.initials: T
authors.lastname: Wang
authors.affiliation: Research Center for High Performance Computing, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China; College of Mathematics and Information Science, Hebei University, Baoding, China.
authors.forename: Yong
authors.initials: Y
authors.lastname: Zhang
authors.affiliation: Department of Computer Science, The University of Hong Kong, Hong Kong, China; Hang Seng Management College, Hong Kong, China.
authors.forename: Francis Y L
authors.initials: FY
authors.lastname: Chin
authors.affiliation: Department of Computer Science, The University of Hong Kong, Hong Kong, China.
authors.forename: Hing-Fung
authors.initials: HF
authors.lastname: Ting
authors.affiliation: School of Computer Science, University of Windsor, Windsor, Canada.
authors.forename: Yung H
authors.initials: YH
authors.lastname: Tsin
authors.affiliation: School of Computing and Informatics, Institut Teknologi Brunei, Gadong, Brunei Darussalam.
authors.forename: Sheung-Hung
authors.initials: SH
authors.lastname: Poon
mesh_terms: D000465:Algorithms; D048088:Informatics / Q000379:methods*