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: 4960
Venue: SIGMOD
Year: 2015
Pagerank: 4.314762e-05
Overall Rank: 9,626 | 33.04%
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,346	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	4.7556749e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-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,041	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
2,521	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.6065919e-05
10,985	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	4.1945683e-05
4,067	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.4795399e-05
4,344	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	6.2744553e-05
11,048	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1945683e-05
8,630	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	4.480887e-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
12,041	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1945683e-05