Open access
Date
2023-06-17Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
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-node m-edge undirected graph, our algorithm computes a DFS in Õ(g√n) depth and using Õ (m + n) work. All prior work either required ω(n) depth, and thus were essentially sequential, or needed a high poly(n) work and thus were far from being work-efficient. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000622469Publication status
publishedExternal links
Book title
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and ArchitecturesPages / Article No.
Publisher
Association for Computing MachineryEvent
Subject
Parallel algorithms; depth-first search; work-efficientOrganisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Funding
853109 - Distributed and Massively Parallel Graph Algorithms (EC)
More
Show all metadata
ETH Bibliography
yes
Altmetrics