Parallelism in Dynamic Graph Algorithms

Explore parallelism in dynamic graph algorithms through this one-hour lecture by Guy Blelloch from Carnegie Mellon University, presented at the Simons Institute. Delve into two innovative approaches that expose significant parallelism in dynamic data structures. First, examine batch dynamic algorithms, where updates and queries are processed in batches, allowing for increased parallelism and potentially reduced overall work. Then, investigate graph streaming algorithms that enable parallel processing of rapid streams of arbitrary queries and updates while maintaining consistent graph views. Learn how these techniques combine ideas from persistent and concurrent data structures to handle asynchronous operations efficiently. Gain insights into overcoming the inherently sequential nature of dynamic data structures and discover new possibilities for parallelism in algorithm design.