Can I read Improved distributed $$\Delta $$-coloring on EtoBox?

Improved distributed $$\Delta $$-coloring by Mohsen Ghaffari; Juho Hirvonen; Fabian Kuhn; Yannic Maus is a Social Sciences article available to read on EtoBox.

What is Improved distributed $$\Delta $$-coloring about?

## Abstract We present a randomized distributed algorithm that computes a $$\Delta $$ Δ -coloring in any non-complete graph with maximum degree $$\Delta \ge 4$$ Δ ≥ 4 in $$O(\log \Delta ) + 2^{O(\sqrt{\log \log n})}$$ O ( log Δ ) + 2 O ( log log n ) rounds, as well as a randomized algorithm that computes a $$\Delta $$ Δ -coloring in $$O((\log \log n)^2)$$ O ( ( log log n ) 2 ) rounds when $$\Delta \in [3, O(1)]$$ Δ ∈ [ 3 , O ( 1 ) ] . Both these algorithms improve on an $$O(\log ^3 n / \log \Delta )$$ O ( log 3 n / log Δ ) -round algorithm of Panconesi and Srinivasan (STOC’93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an $$\Omega (\log \log n)$$ Ω ( log log n ) round lower bound of Brandt et al. (STOC’16).

Who reads Improved distributed $$\Delta $$-coloring?

Author

Mohsen Ghaffari; Juho Hirvonen; Fabian Kuhn; Yannic Maus

Publisher

Springer Science and Business Media LLC

Published

2021

Language

EN

Field

Social Sciences (Physical Sciences)