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

Abstract

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 algorithm, achieving $\tilde{O}(\Delta^2)$ span and $\tilde{O}(m \Delta^2 )$ work both with high probability. These bounds substantially improve over the recent deterministic parallel algorithm of Elkin and Khuzman, which has $\tilde{O}(\Delta^4)$ span and $\tilde{O}(m \Delta^5)$ work. Our deterministic algorithm thus represents a $\tilde{O}(\Delta)$ improvement on span and $\tilde{O}(\Delta^2)$ on work compared to their algorithm, and our randomized algorithm improves the span and work by $\tilde{O}(\Delta^2)$ and $\tilde{O}(\Delta^3)$ factors, respectively. Moreover, our improvements do not come at the expense of larger logarithmic factors.