DBScholar

Back to papers

Efficiently Computing k-Edge Connected Components via Graph Decomposition

Summary: Novel graph-decomposition paradigm for computing k-edge connected components via iterative drilling-down; iterations are bounded by the nesting depth of components (h). Threshold-based per-iteration decomposition runs in O(l|E|) (l small), yielding O(h l|E|) total and major speedups over O(|V|^2|E|+|V|^3 log|V|); evaluated on large real and synthetic graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h89c4b3bb1b29338b
Venue
SIGMOD
Year
2013
Pagerank
6.5173666e-05
Overall Rank
4,567 | 69.39%
DOI
10.1145/2463676.2465323

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{chang_sigmod13,
        title = {{Efficiently Computing k-Edge Connected Components via Graph Decomposition}},
        author = {Chang, Lijun and Yu, Jeffrey Xu and Qin, Lu and Lin, Xuemin and Liu, Chengfei and Liang, Weifa},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465323},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465323},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank Citing Paper Year Venue Pagerank
970 Influential Community Search in Large Networks 2015 VLDB 0.00012749284
1,440 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010630613
2,110 Maximum Co-located Community Search in Large Scale Social Networks 2018 VLDB 9.0222862e-05
2,873 Hierarchical Core Maintenance on Large Dynamic Graphs 2021 VLDB 7.9005874e-05
3,145 Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity 2015 SIGMOD 7.5828479e-05
3,170 On Querying Historical K-Cores 2021 VLDB 7.5572564e-05
3,221 Skyline Community Search in Multi-valued Networks 2018 SIGMOD 7.5060153e-05
3,431 Efficient Size-Bounded Community Search over Large Networks 2021 VLDB 7.2925605e-05
4,180 Global Reinforcement of Social Networks: The Anchored Coreness Problem 2020 SIGMOD 6.7474268e-05
4,779 Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach 2021 VLDB 6.4069971e-05
4,861 An Optimal and Progressive Approach to Online Search of Top-K Influential Communities 2018 VLDB 6.3646812e-05
6,226 I/O Efficient ECC Graph Decomposition via Graph Reduction 2016 VLDB 5.8266364e-05
6,666 Efficient Parallel D-core Decomposition at Scale 2024 VLDB 5.698709e-05
7,649 Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling 2017 SIGMOD 5.4598986e-05
7,891 A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition 2022 VLDB 5.4156949e-05
9,713 Efficient Maximum s-Bundle Search via Local Vertex Connectivity 2025 SIGMOD 5.124163e-05
9,957 Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs 2024 VLDB 5.0910746e-05
10,395 Efficient Querying of Maximum Connectivity-Based Quasi-Cliques in Large Graphs 2027 SIGMOD 4.9605343e-05
10,407 Scaling Up Density Decomposition on Massive Graphs 2027 SIGMOD 4.9605343e-05
10,413 To Learn or Not to Learn? An In-depth Empirical Analysis of Community Search Approaches 2027 SIGMOD 4.9605343e-05
10,596 Zero-Redundancy Search for Bi-Components in Bipartite Graphs 2026 SIGMOD 4.9605343e-05
10,639 Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements 2026 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
255 On Triangulation-based Dense Neighborhood Graph Discovery 2011 VLDB 0.00022949287
643 Finding Maximal Cliques in Massive Networks by H*-graph 2010 SIGMOD 0.00015219469
Previous Page 1 / 1 Next

Semantically Similar Papers