Parallel Batch-Dynamic Graph Representations

Explore efficient methods for representing dynamically changing graphs in this 53-minute lecture by Laxman Dhulipala from the University of Maryland. Delve into the Aspen graph-streaming framework, which extends Ligra's interface with graph update operations. Examine the CPAM framework, offering improved space efficiency and theoretical guarantees through parallel block-based purely-functional data structures. Conclude by investigating practical applications of these data structures in parallel batch-dynamic graph algorithms, such as dynamic connectivity, with a focus on minimizing space overhead.

Parallel Batch-Dynamic Graph Representations