Nearly Work-Efficient Parallel DFS in Undirected Graphs

2023/04/19 by Mohsen Ghaffari, Christoph Grunau, Ghaffari, Mohsen +3 · 5 citations
Engineering · Computer Science · #VLSI and FPGA Design Techniques #Complexity and Algorithms in Graphs #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2304.09774

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 O(√(n)) depth and using O(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.

Cited by

• Dynamic Graph Coloring: Sequential, Parallel, and Distributed
• Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
• Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
• Parallel batch queries on dynamic trees: algorithms and experiments
• Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes

Related

• Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
• Space-Efficient DFS and Applications: Simpler, Leaner, Faster
• Efficient Semi-External Depth-First Search
• Engineering DFS-Based Graph Algorithms
• Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient