Nearly Work-Efficient Parallel DFS in Undirected Graphs

Mohsen Ghaffari, Christoph Grunau, Jiahao Qu

We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any $n$-node $m$-edge undirected grap…