Nearly Work-Efficient Parallel DFS in Undirected Graphs

Ghaffari, M; Grunau, C; Qu, JH

Ghaffari, M (通讯作者),MIT, Cambridge, MA 02139 USA.

PROCEEDINGS OF THE 35TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2023, 2023; (): 273

Abstract

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

Full Text Link