A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition
Summary: Divide-and-conquer construction of the k-ECC hierarchy for all k, with space linear in n. Time: O(log δ(G))·TKECC(G); memory: 2m+O(n log δ(G)); experiments show up to 28× faster runtime and 8× less memory than the state of the art. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Lijun Chang
- 2. Zhiyi Wang
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,922 | BCviz: A Linear-Space Index for Mining and Visualizing Cohesive Bipartite Subgraphs | 2025 | SIGMOD | 5.4076395e-05 |
| 11,051 | Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs | 2024 | VLDB | 5.1725247e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,350 | KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs | 2020 | VLDB | 0.00011168745 |
| 2,152 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 9.1341734e-05 |
| 3,082 | GConnect: A Connectivity Index for Massive Disk-Resident Graphs | 2009 | VLDB | 7.8432697e-05 |
| 3,243 | Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity | 2015 | SIGMOD | 7.6761871e-05 |
| 3,389 | Efficient Size-Bounded Community Search over Large Networks | 2021 | VLDB | 7.5253331e-05 |
| 5,830 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 6.132672e-05 |
| 7,029 | I/O Efficient ECC Graph Decomposition via Graph Reduction | 2016 | VLDB | 5.7754385e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,160 | Accelerating Core Decomposition in Billion-Scale Hypergraphs | 2025 | SIGMOD | 5.371468e-05 |
| 9,612 | Divide & Conquer: I/O Efficient Depth-First Search | 2015 | SIGMOD | 5.3056412e-05 |
| 3,938 | Efficient k-Clique Listing: An Edge-Oriented Branching Strategy | 2024 | SIGMOD | 7.0733005e-05 |
| 1,654 | Distance-generalized Core Decomposition | 2019 | SIGMOD | 0.00010178111 |
| 12,049 | I/O Efficient: Computing SCCs in Massive Graphs | 2013 | SIGMOD | 5.1725247e-05 |
| 3,243 | Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity | 2015 | SIGMOD | 7.6761871e-05 |
| 2,152 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 9.1341734e-05 |
| 4,817 | Efficient Maximum k-Defective Clique Computation with Improved Time Complexity | 2023 | SIGMOD | 6.5611315e-05 |
| 7,029 | I/O Efficient ECC Graph Decomposition via Graph Reduction | 2016 | VLDB | 5.7754385e-05 |
| 5,830 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 6.132672e-05 |