English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Distributed graph coloring is one of the most extensively studied problems indistributed computing. There is a canonical family of distributed graphcoloring algorithms known as the locally-iterative coloring algorithms, firstformalized in the seminal work of [Szegedy and Vishwanathan, STOC'93]. In suchalgorithms, every vertex iteratively updates its own color according to apredetermined function of the current coloring of its local neighborhood. Dueto the simplicity and naturalness of its framework, locally-iterative coloringalgorithms are of great significance both in theory and practice. In thispaper, we give a locally-iterative $(\Delta+1)$-coloring algorithm with$O(\Delta^{3/4}\log\Delta)+\log^*n$ running time. This is the firstlocally-iterative $(\Delta+1)$-coloring algorithm with sublinear-in-$\Delta$running time, and answers the main open question raised in a recentbreakthrough [Barenboim, Elkin, and Goldberg, JACM'21]. A key component of ouralgorithm is a locally-iterative procedure that transforms an$O(\Delta^2)$-coloring to a $(\Delta+O(\Delta^{3/4}\log\Delta))$-coloring in$o(\Delta)$ time. Inside this procedure we work on special proper coloringsthat encode (arb)defective colorings, and reduce the number of used colorsquadratically in a locally-iterative fashion. As a main application of ourresult, we also give a self-stabilizing distributed algorithm for$(\Delta+1)$-coloring with $O(\Delta^{3/4}\log\Delta)+\log^*n$ stabilizationtime. To the best of our knowledge, this is the first self-stabilizingalgorithm for $(\Delta+1)$-coloring with sublinear-in-$\Delta$ stabilizationtime.

Locally-iterative $(\Delta+1)$-Coloring in Sublinear (in $\Delta$) Rounds