TY - JOUR
T1 - A simple algorithm for finding all k-edge-connected components
AU - Wang, Tianhao
AU - Zhang, Yong
AU - Chin, Francis Y.L.
AU - Ting, Hing Fung
AU - Tsin, Yung H.
AU - Poon, Sheung Hung
N1 - Publisher Copyright:
© 2015 Wang et al.
PY - 2015/9/14
Y1 - 2015/9/14
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84947460420&partnerID=8YFLogxK
U2 - 10.1371/journal.pone.0136264
DO - 10.1371/journal.pone.0136264
M3 - Article
C2 - 26368134
AN - SCOPUS:84947460420
SN - 1932-6203
VL - 10
JO - PLoS ONE
JF - PLoS ONE
IS - 9
M1 - e0136264
ER -