4 papers
Parallel Batch-Dynamic Maximal Independent Set
Guy Blelloch, Andrew Brady, Laxman Dhulipala +2
We develop the first theoretically-efficient algorithm for maintaining the maximal independent set (MIS) of a graph in the parallel batch-dynamic setting. In this setting, a graph…
Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation
Guy Blelloch, Andrew Brady, Laxman Dhulipala +3
A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can…
Parallel Batch-Dynamic Maximal Matching with Constant Work per Update
Guy E. Blelloch, Andrew C. Brady
We present a work optimal algorithm for parallel fully batch-dynamic maximal matching against an oblivious adversary. It processes batches of updates (either insertions or deletion…
Parallel batch queries on dynamic trees: algorithms and experiments
Humza Ikram, Andrew Brady, Daniel Anderson +1
Dynamic tree data structures maintain a forest while supporting insertion and deletion of edges and a broad set of queries in time per operation. Such data structures a…