Vi ger en ny randomiserad distribuerad algoritm för (Δ + 1)-färgning i LOCAL-modellen, som körs i O (logg Δ) + 2 O ( Δ log log n) rundor i en graf av maximal grad Δ. Detta innebär att (Δ + 1)-färg problemet är enklare än maximal oberoende uppsättning problem och maximal matchning problem, på grund av deras nedre gränser av  och (min( log n log n, log Δ log Δ )) av Kuhn, Moscibroda, och Wattenhofer [PODC'04]. Vår algoritm sträcker sig också till list-färgning där paletten för varje nod innehåller Δ + 1 färger. Vi utökar uppsättningen distribuerade symmetri-brytande tekniker genom att utföra en nedbrytning av grafer i täta och glesa delar. Utmatning. En r - round algoritm i LOCAL- modellen innebär att varje vertex endast använder information i sin r - neighborhood för att beräkna utdata, och vice versa. Graffärgning är ett av de centrala problemen med grafteori, med många tillämpningar till algoritmer och kombinatorik. Färgproblemet (Δ + 1) är det mest berömda fallet, eftersom det för varje graf finns en (Δ + 1)-färgning, som kan hittas via en enkel (sekvens) girig algoritm. Dessutom, även om Δ-färger finns för vissa grafer, finns det exempel där det inte kan lösas lokalt; till exempel, 2-färgning en ring kräver  och (n) rundor. Vertex-färgning i den distribuerade modellen, särskilt, har applikationer som en subrutin i andra distribuerade algoritmer (t.ex. Lovász Local Lemma [19] ) och schemaläggningsproblem (t.ex. radionät sändningar [13, 15, 18, 46] ). Det är typiskt i sådana tillämpningar att lösningens kvalitet beror på antalet färger som används. Därför är (Δ + 1)-färgning ett naturligt problem, eftersom det leder till de optimala scheman som man kan hoppas kunna garantera som en funktion av Δ.
ε log log n) rundor med hög sannolikhet REF.
Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}