arXiv Open Access 2020

Coloring Fast Without Learning Your Neighbors' Colors

Magnus M. Halldorsson Fabian Kuhn Yannic Maus Alexandre Nolin

Lihat Sumber

Abstrak

We give an improved randomized CONGEST algorithm for distance-$2$ coloring that uses $Δ^2+1$ colors and runs in $O(\log n)$ rounds, improving the recent $O(\log Δ\cdot \log n)$-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$.

Topik & Kata Kunci

cs.DC cs.DS

Penulis (4)

Magnus M. Halldorsson

Fabian Kuhn

Yannic Maus

Alexandre Nolin

Format Sitasi

APA MLA BibTeX

Halldorsson, M.M., Kuhn, F., Maus, Y., Nolin, A. (2020). Coloring Fast Without Learning Your Neighbors' Colors. https://arxiv.org/abs/2008.04303

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓