I/O Efficient ECC Graph Decomposition via Graph Reduction

Summary: I/O efficient ECC decomposition for all k values achieved via two graph-reduction operators that shrink the in-memory graph while preserving k-edge connectivity. Bottom-Up, Top-Down, and Hybrid algorithms explore k-values in different orders to minimize redundant work, with experiments on graphs up to 1.95B edges demonstrating scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11343
Venue: VLDB
Year: 2016
Pagerank: 4.7511136e-05
Overall Rank: 7,343 | 48.97%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5600506e-05
3,323	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.2170169e-05
4,737	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	5.9529218e-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
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-05
10,544	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	4.1905499e-05
10,591	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	4.1905499e-05
10,689	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047955011
588	Massive Graph Triangulation	2013	SIGMOD	0.00019588834
682	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.0001816451
734	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017419528
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
6,206	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1522897e-05
9,626	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD	4.3106273e-05
12,049	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.380727e-05
10,159	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.1905499e-05
3,857	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	6.6924202e-05
11,051	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1905499e-05
9,626	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD	4.3106273e-05
4,984	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	5.7811667e-05
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141
12,049	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1905499e-05
8,630	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	4.4765914e-05
6,206	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1522897e-05