Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation
arXiv:2602.17811v1 Announce Type: new Abstract: 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 insert or delete batches of edges, and the goal is to process the entire batch in parallel with work per edge similar to that of a single sequential update and with span (or depth) for the entire batch that is polylogarithmic. In this paper […]