Parallel Algorithms for Depth-First Search

In this paper we examine parallel algorithms for performing a depth-first search (DFS) of a directed or undirected graph in sub-linear time. this subject is interesting in part because DFS seemed at first to be an inherently sequential process, and for a long time many researchers believed that no such algorithms existed. We survey three seminal papers on the subject. The first one proves that a special case of DFS is (in all likelihood) inherently sequential; the second shows that DFS for planar undirected graphs is in NC; and the third shows that DFS for general undirected graphs is in RNC. We also discuss randomnized algorithms, P-completeness and matching, three topics that are essential for understanding and appreciating the results in these papers.