Faster parallel methods improve edge coloring in complex networks
More Efficient Parallel $(Δ+1)$-Edge Coloring
Data Structures and Algorithms
Summary
Coloring edges in a network means assigning colors so no two connected edges share the same one, which is useful for organizing tasks or resources. The paper presents two new ways to do this quickly and in parallel, especially when the network connections get complicated. One method guarantees results, while the other uses randomness for an even faster solution. Both methods improve significantly on earlier techniques in terms of speed and efficiency.
What this means in practice
- •For network schedulers: Allocate communication channels faster by coloring network links without conflicts using the improved parallel algorithms.
- •For parallel computing engineers: Speed up resource assignment tasks by implementing the new efficient parallel edge coloring methods in hardware or software.
Authors
Jeremy T. Fineman, Seyed Ali Mohammadi
Abstract
This paper gives two parallel algorithms for $Δ+1$ edge coloring, where $Δ$ denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O}(Δ^3)$ span and $\tilde{O}(m Δ^3)$ work. Our second algorithm and our main result is a more efficient randomized algorithm, achieving $\tilde{O}(Δ^2)$ span and $\tilde{O}(m Δ^2 )$ work both with high probability. These bounds substantially improve over the recent deterministic parallel algorithm of Elkin and Khuzman, which has $\tilde{O}(Δ^4)$ span and $\tilde{O}(m Δ^5)$ work. Our deterministic algorithm thus represents a $\tilde{O}(Δ)$ improvement on span and $\tilde{O}(Δ^2)$ on work compared to their algorithm, and our randomized algorithm improves the span and work by $\tilde{O}(Δ^2)$ and $\tilde{O}(Δ^3)$ factors, respectively. Moreover, our improvements do not come at the expense of larger logarithmic factors.