Metraipolis › archive › dc_bbd050d57e39
More Efficient Parallel $(Δ+1)$-Edge Coloring — arXiv:2609.35693
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35693
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:19:04.354Z
- SHA-256 of the archived text
e834f9b759f6c4e5e74d12d39e3e4eb0332b20c8614a741e8933fe77745ccd2a- Stable URL of this page
https://metraipolis.com/documento/dc_bbd050d57e39
How to cite
More Efficient Parallel $(Δ+1)$-Edge Coloring — arXiv:2609.35693 — arXiv (en), https://arxiv.org/abs/2609.35693 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bbd050d57e39 (Metraipolis archive dc_bbd050d57e39, sha256 e834f9b759f6c4e5e74d12d39e3e4eb0332b20c8614a741e8933fe77745ccd2a)
BibTeX
@misc{dcbbd050d57e39,
title = {More Efficient Parallel $(Δ+1)$-Edge Coloring — arXiv:2609.35693},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35693},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bbd050d57e39; sha256 e834f9b759f6c4e5e74d12d39e3e4eb0332b20c8614a741e8933fe77745ccd2a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35693. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.35693 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:56:21.786Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).