Parallel Graph Algorithms
summary
Survey of concrete parallel methods for directed reachability and SSSP that states costs and limits: Spencer's algorithm increases outdegree via two-hop shortcutting and yields n rho^2 + m work, span n/rho (set rho≈√n gives n^2 work, √n span); sampling/shortcutting (Ullman–Yannakakis) gives m sqrt(n) work, span sqrt(n) for unweighted graphs; a linear-time n^{2/3} shortcutting algorithm exists, Jambulapati–Liu–Sidford improve toward ~√n, an n^{1/3} diameter is possible but not yet efficient; construction uses hop-limited BFS, low-diameter decompositions, hopsets, and is Monte Carlo (reachability becomes Las Vegas); not implemented and constants look large.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:05Parallel graph algorithms overview
- 3:11Single-source reachability
- 6:23Spencer's reachability algorithm
- 14:51Shortcutting graphs
- 24:12Divide-and-conquer shortcutting
- 35:41Parallelizing divide-and-conquer
- 43:36Hop-limited reachability
- 50:57Reachability trade-offs
- 53:43Single-source shortest paths
- 1:03:50Questions and discussion
related talks
01h 03mIntro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms
01h 05mThink Parallel
49mStriving to Make Things Simple and Fast
39mThe best multicore-parallelization refactoring you've never heard of
23mConnectivity Graphs: A Method for Proving Deadlock Freedom Based on Separation L
43mParallel Algorithms: Work Smarter, Not Harder
15mRON: One-Way Circular Shortest Routing to Achieve Efficient and Bounded-waiting Spinlocks
48m“Is Parallel Programming still hard? PART 2 of 2”