Jeremy T. Fineman

More Efficient Parallel $(\Delta+1)$-Edge Coloring

This paper gives two parallel algorithms for $\Delta+1$ edge coloring, where $\Delta$ denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O}(\Delta^3)$ span and $\tilde{O}(m \Delta^3)$ work. Our second algorithm and our main result is a more efficient randomized algori...