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-07-29
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013002434OK.pdf547.94 kB
Adobe PDF
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: