In this talk I will describe recent work on efficiently representing graphs undergoing dynamic changes. In particular, I will describe Apsen, a graph-streaming framework that extends the interface of Ligra with operations for updating graphs and (2) the CPAM framework, which enables faster and more space-efficient representations with better theoretical guarantees using a parallel block-based purely-functional data structure. I will end by describing ongoing work on using these data structures in practical parallel batch-dynamic graph algorithms such as dynamic connectivity, with low overall space-overheads.

Video Recording