Parallelism in Dynamic Graph Algorithms
summary
Shows concrete parallel algorithms and costs: a batch incremental MST that prunes and compresses the tree with an RC-tree hierarchy and runs in about k log(n/k) work and polylog span, a method for mixed offline sequences of updates and queries that executes in k log n work with polylog depth by merging timestamps through the balanced RC/top-tree, and a concurrent streaming design using partial copying and persistence that gives wait-free queries and constant-time updates while providing consistent snapshots.
AI-written summary Β· about