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 graph, our algorithm computes a DFS in $\tilde{O}(\sqrt{n})$ depth and using $\tilde{O}(m+n)$ work. All prior work either required $\Omega(n)$ depth, and thus were essentially sequential, or needed a high $poly(n)$ work and thus were far from being work-efficient.

翻译：我们提出了第一个用于无向图的并行深度优先搜索算法，该算法具有几乎线性的工作量和亚线性的深度。具体而言，在任何 $n$-结点，$m$-边的无向图中，我们的算法使用 $\tilde {O}(\sqrt{n})$ 的深度和 $\tilde {O}(m+n)$ 的工作量计算 DFS。所有先前的工作要么需要 $\Omega(n)$ 的深度，因此本质上是顺序的，要么需要高 $poly(n)$的工作量，因此远未达到工作效率。