ALCOMFT-TR-02-49

Jop Sibeyn, James Abello and Ulrich Meyer
Heuristics for Semi-External Depth First Search on Directed Graphs
MPI. Work package 1. May 2002.

Abstract: Computing the strong components of a directed graph is an essential operation for a basic structural analysis of it. This problem can be solved by twice running a depth-first search (DFS). In an external setting, in which no longer all data can be stored in the main memory, the DFS problem is unsolved so far. Assuming that node-related data can be stored internally, semi-external computing, does not make the problem substantially easier. Considering the definite need to analyze very large graphs (web graph, telephone call graphs, \dots), we have developed a set of heuristics which together allow to perform semi-external DFS for directed graphs in practice. The heuristics have been applied to graphs with very different graph properties, including ``web graphs'' as described in the most recent literature (which are not exceptionally hard) and some call graphs from ATT. The program is typically about 100 times faster than the best alternative, a factor that will further increase with future technology developments.

Postscript file: ALCOMFT-TR-02-49.ps.gz (96 kb).