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 palette size as a function of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows.Lower Bounds: First, we simplify the round elimination technique of Brandt et al. [16] and prove that (2Δ −2)-edge coloring requires Ω (logΔ log n) time with high probability and Ω (logΔ n) time deterministically, even on trees. Second, we show that a natural approach to computing (Δ +1)-edge colorings (Vizing’s theorem), namely, extending an arbitrary partial coloring by iteratively recoloring subgraphs, requires Ω (Δ log n) time.Upper Bounds on General Graphs: We give a randomized edge coloring algorithm that can use palette sizes as small as Δ + Õ(&sqrt;Δ), which is a natural barrier for randomized approaches. The running time of our (1+ε)Δ-edge coloring algorithm is usually dominated by O(\log ε−1) calls to a distributed Lovász local lemma (LLL) algorithm. For example, using the Chung-Pettie-Su LLL algorithm, we compute a (1+ε)Δ-edge coloring in O(log n) time when ε ≥ (log3 Δ) / &sqrt; Δ , or O(logΔ n) + (log log n)3 + o(1) time when ε = Ω (1). When Δ is sublogarithmic in n the performance is improved with the Ghaffari-Harris-Kuhn LLL algorithm.Upper Bounds on Trees: We show that the Ω (logΔ log n) lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which arise naturally from O(1)-round probabilistic algorithms run on trees. Specifically, our (1+ε)Δ-edge coloring algorithm for trees takes O(log (1 / ε)) ⋅ max { log log n\ log log log n, loglog Δ log n} time when ε ≥ (log3 Δ) / &sqrt; Δ, or O(max { log log n\ log log log n, logΔ log n}) time when ε = Ω (1).

Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma