Efficiently computing k-edge connected components via graph decomposition
- Publication Type:
- Conference Proceeding
- Citation:
- Proceedings of the ACM SIGMOD International Conference on Management of Data, 2013, pp. 205 - 216
- Issue Date:
- 2013-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2013002434OK.pdf | 547.94 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Efficiently computing k-edge connected components in a large graph, G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimization algorithms. Consider existing techniques for computing k-edge connected components are quite time consuming and are unlikely to be scalable for large scale graphs, in this paper we firstly propose a novel graph decomposition paradigm to iteratively decompose a graph G for computing its k-edge connected components such that the number of drilling-down iterations h is bounded by the "depth" of the k-edge connected components nested together to form G, where h usually is a small integer in practice. Secondly, we devise a novel, efficient threshold-based graph decomposition algorithm, with time complexity O(l × |E|), to decompose a graph G at each iteration, where l usually is a small integer with l ≪ |V|. As a result, our algorithm for computing k-edge connected components significantly improves the time complexity of an existing state-of-the-art technique from O(|V|2|E| + |V|3log|V|) to O(h×l× |E|). Finally, we conduct extensive performance studies on large real and synthetic graphs. The performance studies demonstrate that our techniques significantly outperform the state-of-the-art solution by several orders of magnitude. Copyright © 2013 ACM.
Please use this identifier to cite or link to this item: