A Simple Algorithm for Finding All k-edge-connected Components
文献类型：期刊论文
| 作者 | Tianhao Wang; Yong Zhang; Francis Y. L. Chin; Hing-Fung Ting; Yung H. Tsin; Sheung-Hung Poon |
| 刊名 | PLoS ONE
 |
| 出版日期 | 2015 |
| 英文摘要 | 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 = jVj. 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. |
| 收录类别 | SCI |
| 原文出处 | http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264 |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/6871]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | PLoS ONE |
| 推荐引用方式 GB/T 7714 | Tianhao Wang,Yong Zhang,Francis Y. L. Chin,et al. A Simple Algorithm for Finding All k-edge-connected Components[J]. PLoS ONE,2015. |
| APA | Tianhao Wang,Yong Zhang,Francis Y. L. Chin,Hing-Fung Ting,Yung H. Tsin,&Sheung-Hung Poon.(2015).A Simple Algorithm for Finding All k-edge-connected Components.PLoS ONE. |
| MLA | Tianhao Wang,et al."A Simple Algorithm for Finding All k-edge-connected Components".PLoS ONE (2015). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。