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…