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,897 | BCviz: A Linear-Space Index for Mining and Visualizing Cohesive Bipartite Subgraphs | 2025 | SIGMOD | 4.427232e-05 |
| 11,048 | Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs | 2024 | VLDB | 4.1945683e-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,570 | KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs | 2020 | VLDB | 0.00011322927 |
| 2,512 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 8.6196023e-05 |
| 3,020 | GConnect: A Connectivity Index for Massive Disk-Resident Graphs | 2009 | VLDB | 7.6992238e-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 |
| 6,207 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 5.1572428e-05 |
| 7,346 | I/O Efficient ECC Graph Decomposition via Graph Reduction | 2016 | VLDB | 4.7556749e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,146 | Accelerating Core Decomposition in Billion-Scale Hypergraphs | 2025 | SIGMOD | 4.3849295e-05 |
| 9,626 | Divide & Conquer: I/O Efficient Depth-First Search | 2015 | SIGMOD | 4.314762e-05 |
| 4,270 | Efficient k-Clique Listing: An Edge-Oriented Branching Strategy | 2024 | SIGMOD | 6.3067205e-05 |
| 1,836 | Distance-generalized Core Decomposition | 2019 | SIGMOD | 0.00010365753 |
| 12,041 | I/O Efficient: Computing SCCs in Massive Graphs | 2013 | SIGMOD | 4.1945683e-05 |
| 3,854 | Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity | 2015 | SIGMOD | 6.6988744e-05 |
| 2,512 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 8.6196023e-05 |
| 4,984 | Efficient Maximum k-Defective Clique Computation with Improved Time Complexity | 2023 | SIGMOD | 5.7867286e-05 |
| 7,346 | I/O Efficient ECC Graph Decomposition via Graph Reduction | 2016 | VLDB | 4.7556749e-05 |
| 6,207 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 5.1572428e-05 |