Efficient Parallel $(Δ+1)$-Edge-Coloring
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911387104575488 |
|---|---|
| author | Elkin, Michael Khuzman, Ariel |
| author_facet | Elkin, Michael Khuzman, Ariel |
| contents | We study the $(Δ+1)$-edge-coloring problem in the parallel $\left(\mathrm{PRAM}\right)$ model of computation. The celebrated Vizing's theorem [Viz64] states that every simple graph $G = (V,E)$ can be properly $(Δ+1)$-edge-colored. In a seminal paper, Karloff and Shmoys [KS87] devised a parallel algorithm with time $O\left(Δ^5\cdot\log n\cdot\left(\log^3 n+Δ^2\right)\right)$ and $O(m\cdotΔ)$ processors. This result was improved by Liang et al. [LSH96] to time $O\left(Δ^{4.5}\cdot \log^3Δ\cdot \log n + Δ^4 \cdot\log^4 n\right)$ and $O\left(n\cdotΔ^{3} +n^2\right)$ processors. [LSH96] claimed $O\left(Δ^{3.5} \cdot\log^3Δ\cdot \log n + Δ^3\cdot \log^4 n\right)$ time, but we point out a flaw in their analysis, which once corrected, results in the above bound. We devise a faster parallel algorithm for this fundamental problem. Specifically, our algorithm uses $O\left(Δ^4\cdot \log^4 n\right)$ time and $O(m\cdot Δ)$ processors. Another variant of our algorithm requires $O\left(Δ^{4+o(1)}\cdot\log^2 n\right)$ time, and $O\left(m\cdotΔ\cdot\log n\cdot\log^δΔ\right)$ processors, for an arbitrarily small $δ>0$. We also devise a few other tradeoffs between the time and the number of processors, and devise an improved algorithm for graphs with small arboricity. On the way to these results, we also provide a very fast parallel algorithm for updating $(Δ+1)$-edge-coloring. Our algorithm for this problem is dramatically faster and simpler than the previous state-of-the-art algorithm (due to [LSH96]) for this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_13822 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Efficient Parallel $(Δ+1)$-Edge-Coloring Elkin, Michael Khuzman, Ariel Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Discrete Mathematics We study the $(Δ+1)$-edge-coloring problem in the parallel $\left(\mathrm{PRAM}\right)$ model of computation. The celebrated Vizing's theorem [Viz64] states that every simple graph $G = (V,E)$ can be properly $(Δ+1)$-edge-colored. In a seminal paper, Karloff and Shmoys [KS87] devised a parallel algorithm with time $O\left(Δ^5\cdot\log n\cdot\left(\log^3 n+Δ^2\right)\right)$ and $O(m\cdotΔ)$ processors. This result was improved by Liang et al. [LSH96] to time $O\left(Δ^{4.5}\cdot \log^3Δ\cdot \log n + Δ^4 \cdot\log^4 n\right)$ and $O\left(n\cdotΔ^{3} +n^2\right)$ processors. [LSH96] claimed $O\left(Δ^{3.5} \cdot\log^3Δ\cdot \log n + Δ^3\cdot \log^4 n\right)$ time, but we point out a flaw in their analysis, which once corrected, results in the above bound. We devise a faster parallel algorithm for this fundamental problem. Specifically, our algorithm uses $O\left(Δ^4\cdot \log^4 n\right)$ time and $O(m\cdot Δ)$ processors. Another variant of our algorithm requires $O\left(Δ^{4+o(1)}\cdot\log^2 n\right)$ time, and $O\left(m\cdotΔ\cdot\log n\cdot\log^δΔ\right)$ processors, for an arbitrarily small $δ>0$. We also devise a few other tradeoffs between the time and the number of processors, and devise an improved algorithm for graphs with small arboricity. On the way to these results, we also provide a very fast parallel algorithm for updating $(Δ+1)$-edge-coloring. Our algorithm for this problem is dramatically faster and simpler than the previous state-of-the-art algorithm (due to [LSH96]) for this problem. |
| title | Efficient Parallel $(Δ+1)$-Edge-Coloring |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Discrete Mathematics |
| url | https://arxiv.org/abs/2601.13822 |