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
- 4731
- Venue
- SIGMOD
- Year
- 2013
- Pagerank
- 5.1522897e-05
- Overall Rank
- 6,206 | 56.87%
- 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,256 |
Influential Community Search in Large Networks |
2015 |
VLDB |
0.00013009097 |
| 1,670 |
Speedup Graph Processing by Graph Ordering |
2016 |
SIGMOD |
0.00010944596 |
| 2,608 |
Maximum Co-located Community Search in Large Scale Social Networks |
2018 |
VLDB |
8.4587487e-05 |
| 3,274 |
Global Reinforcement of Social Networks: The Anchored Coreness Problem |
2020 |
SIGMOD |
7.2886717e-05 |
| 3,323 |
Hierarchical Core Maintenance on Large Dynamic Graphs |
2021 |
VLDB |
7.2170169e-05 |
| 3,608 |
Skyline Community Search in Multi-valued Networks |
2018 |
SIGMOD |
6.9241653e-05 |
| 3,857 |
Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity |
2015 |
SIGMOD |
6.6924202e-05 |
| 3,972 |
Efficient Size-Bounded Community Search over Large Networks |
2021 |
VLDB |
6.5724209e-05 |
| 4,133 |
On Querying Historical K-Cores |
2021 |
VLDB |
6.4185206e-05 |
| 5,148 |
Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach |
2021 |
VLDB |
5.6572863e-05 |
| 5,656 |
An Optimal and Progressive Approach to Online Search of Top-K Influential Communities |
2018 |
VLDB |
5.3876479e-05 |
| 6,509 |
Efficient Parallel D-core Decomposition at Scale |
2024 |
VLDB |
5.0273291e-05 |
| 7,343 |
I/O Efficient ECC Graph Decomposition via Graph Reduction |
2016 |
VLDB |
4.7511136e-05 |
| 7,664 |
Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling |
2017 |
SIGMOD |
4.6805647e-05 |
| 8,630 |
A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition |
2022 |
VLDB |
4.4765914e-05 |
| 9,396 |
Efficient Maximum s-Bundle Search via Local Vertex Connectivity |
2025 |
SIGMOD |
4.3399748e-05 |
| 10,076 |
Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements |
2026 |
SIGMOD |
4.1905499e-05 |
| 11,051 |
Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs |
2024 |
VLDB |
4.1905499e-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