1 citations · 1 across the 3 of their papers we have counts for
4 papers · 1 filter
Deterministic and Work-Efficient Parallel Batch-Dynamic Trees in Low Span
Daniel Anderson, Guy E. Blelloch
Dynamic trees are a well-studied and fundamental building block of dynamic graph algorithms dating back to the seminal work of Sleator and Tarjan [STOC'81, (1981), pp. 114-122]. Th…
Work-efficient Batch-incremental Minimum Spanning Trees with Applications to the Sliding Window Model
Daniel Anderson, Guy E. Blelloch, Kanat Tangwongsan
Algorithms for dynamically maintaining minimum spanning trees (MSTs) have received much attention in both the parallel and sequential settings. While previous work has given optima…
Parallel Batch-dynamic Trees via Change Propagation
Umut A. Acar, Daniel Anderson, Guy E. Blelloch +2
The dynamic trees problem is to maintain a forest subject to edge insertions and deletions while facilitating queries such as connectivity, path weights, and subtree weights. Dynam…
Parallel Batch-Dynamic Graph Connectivity
Umut A. Acar, Daniel Anderson, Guy E. Blelloch +1
In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. Th…