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

The complexity of distributed edge coloring depends heavily on the palettesize as a function of the maximum degree $\Delta$. In this paper we explore thecomplexity of edge coloring in the LOCAL model in different palette sizeregimes.  1. We simplify the \emph{round elimination} technique of Brandt et al. andprove that $(2\Delta-2)$-edge coloring requires $\Omega(\log_\Delta \log n)$time w.h.p. and $\Omega(\log_\Delta n)$ time deterministically, even on trees.The simplified technique is based on two ideas: the notion of an irregularrunning time and some general observations that transform weak lower boundsinto stronger ones.  2. We give a randomized edge coloring algorithm that can use palette sizes assmall as $\Delta + \tilde{O}(\sqrt{\Delta})$, which is a natural barrier forrandomized approaches. The running time of the algorithm is at most$O(\log\Delta \cdot T_{LLL})$, where $T_{LLL}$ is the complexity of apermissive version of the constructive Lovasz local lemma.  3. We develop a new distributed Lovasz local lemma algorithm fortree-structured dependency graphs, which leads to a $(1+\epsilon)\Delta$-edgecoloring algorithm for trees running in $O(\log\log n)$ time. This algorithmarises from two new results: a deterministic $O(\log n)$-time LLL algorithm fortree-structured instances, and a randomized $O(\log\log n)$-time graphshattering method for breaking the dependency graph into independent $O(\logn)$-size LLL instances.  4. A natural approach to computing $(\Delta+1)$-edge colorings (Vizing'stheorem) is to extend partial colorings by iteratively re-coloring parts of thegraph. We prove that this approach may be viable, but in the worst caserequires recoloring subgraphs of diameter $\Omega(\Delta\log n)$. This standsin contrast to distributed algorithms for Brooks' theorem, which exploit theexistence of $O(\log_\Delta n)$-length augmenting paths.

The Complexity of Distributed Edge Coloring with Small Palettes