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.4229886e-05 |
| 11,051 | Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs | 2024 | VLDB | 4.1905499e-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.00011311977 |
| 2,516 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 8.6114467e-05 |
| 3,024 | GConnect: A Connectivity Index for Massive Disk-Resident Graphs | 2009 | VLDB | 7.691835e-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 |
| 6,206 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 5.1522897e-05 |
| 7,343 | I/O Efficient ECC Graph Decomposition via Graph Reduction | 2016 | VLDB | 4.7511136e-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.380727e-05 |
| 9,626 | Divide & Conquer: I/O Efficient Depth-First Search | 2015 | SIGMOD | 4.3106273e-05 |
| 4,266 | Efficient k-Clique Listing: An Edge-Oriented Branching Strategy | 2024 | SIGMOD | 6.3006582e-05 |
| 1,837 | Distance-generalized Core Decomposition | 2019 | SIGMOD | 0.00010355705 |
| 12,049 | I/O Efficient: Computing SCCs in Massive Graphs | 2013 | SIGMOD | 4.1905499e-05 |
| 3,857 | Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity | 2015 | SIGMOD | 6.6924202e-05 |
| 2,516 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 8.6114467e-05 |
| 4,984 | Efficient Maximum k-Defective Clique Computation with Improved Time Complexity | 2023 | SIGMOD | 5.7811667e-05 |
| 7,343 | I/O Efficient ECC Graph Decomposition via Graph Reduction | 2016 | VLDB | 4.7511136e-05 |
| 6,206 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 5.1522897e-05 |