Divide & Conquer: I/O Efficient Depth-First Search

Summary: IO-efficient semi-external DFS on disk graphs via divide-and-conquer: split G into subgraphs, compute local DFS trees in memory, then merge to a global DFS-Tree. Proposes Divide-Star and Divide-TD schemes with a merge, validates correctness, and demonstrates I/O gains on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4961
Venue: SIGMOD
Year: 2015
Pagerank: 5.3056412e-05
Overall Rank: 9,612 | 33.20%
DOI: 10.1145/2723372.2723740

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,029	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	5.7754385e-05
9,479	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.3246578e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12,049	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	5.1725247e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,152	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.1341734e-05
2,461	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.6210174e-05
10,988	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	5.1725247e-05
3,794	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	7.1757545e-05
3,690	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	7.2600845e-05
11,051	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.1725247e-05
8,507	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	5.4820925e-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
12,049	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	5.1725247e-05