69 citations · 144 across the 20 of their papers we have counts for
3 papers · 1 filter
More Efficient Parallel -Edge Coloring
Jeremy T. Fineman, Seyed Ali Mohammadi
This paper gives two parallel algorithms for edge coloring, where denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O…
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…