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
- 4730
- Venue
- SIGMOD
- Year
- 2013
- Pagerank
- 5.1572428e-05
- Overall Rank
- 6,207 | 56.82%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 18 of 18 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 1,257 |
Influential Community Search in Large Networks |
2015 |
VLDB |
0.00013020648 |
| 1,676 |
Speedup Graph Processing by Graph Ordering |
2016 |
SIGMOD |
0.00010946423 |
| 2,603 |
Maximum Co-located Community Search in Large Scale Social Networks |
2018 |
VLDB |
8.4666465e-05 |
| 3,273 |
Global Reinforcement of Social Networks: The Anchored Coreness Problem |
2020 |
SIGMOD |
7.2956944e-05 |
| 3,321 |
Hierarchical Core Maintenance on Large Dynamic Graphs |
2021 |
VLDB |
7.223972e-05 |
| 3,603 |
Skyline Community Search in Multi-valued Networks |
2018 |
SIGMOD |
6.9306814e-05 |
| 3,854 |
Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity |
2015 |
SIGMOD |
6.6988744e-05 |
| 3,969 |
Efficient Size-Bounded Community Search over Large Networks |
2021 |
VLDB |
6.5787567e-05 |
| 4,139 |
On Querying Historical K-Cores |
2021 |
VLDB |
6.415046e-05 |
| 5,149 |
Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach |
2021 |
VLDB |
5.6627295e-05 |
| 5,643 |
An Optimal and Progressive Approach to Online Search of Top-K Influential Communities |
2018 |
VLDB |
5.3928286e-05 |
| 6,513 |
Efficient Parallel D-core Decomposition at Scale |
2024 |
VLDB |
5.0321577e-05 |
| 7,346 |
I/O Efficient ECC Graph Decomposition via Graph Reduction |
2016 |
VLDB |
4.7556749e-05 |
| 7,673 |
Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling |
2017 |
SIGMOD |
4.6826056e-05 |
| 8,630 |
A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition |
2022 |
VLDB |
4.480887e-05 |
| 9,390 |
Efficient Maximum s-Bundle Search via Local Vertex Connectivity |
2025 |
SIGMOD |
4.3441378e-05 |
| 10,076 |
Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements |
2026 |
SIGMOD |
4.1945683e-05 |
| 11,048 |
Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs |
2024 |
VLDB |
4.1945683e-05 |
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.
Semantically Similar Papers