Komplexiteten i distribuerade kantfärgning beror starkt på palettstorleken som en funktion av den maximala graden  på. I detta papper utforskar vi komplexiteten i kantfärgning i LOCAL-modellen i olika palettstorlekssystem. Våra resultat är som följer. • Vi förenklar den runda elimineringstekniken för Brandt et al. [9] och bevisa att (2 ska − 2) kantfärgning kräver  och (log  på log n) tid w.h.p. och... (logga n) tid deterministiskt, även på träd. Den förenklade tekniken bygger på två idéer: föreställningen om en oregelbunden körtid (där nätverkskomponenter avslutar algoritmen vid föreskrivna, men oregelbundna tider) och några allmänna observationer som omvandlar svaga lägre gränser till starkare. • Vi ger en randomiserad kantfärgsalgoritm som kan använda palettstorlekar som är så små som  på + O ( ε) vilket är en naturlig barriär för randomiserade tillvägagångssätt. Körtiden för algoritmen är som mest O(logga) · T LLL ), där T LLL är komplexiteten i en efterlåten version av den konstruktiva Lovász lokala lemma. • Vi utvecklar en ny distribuerad Lovász lokal lemma-algoritm för trädstrukturerade beroendegrafik, vilket leder till en (1 + )-kantig färgalgoritm för träd som körs i O (logglogg n) tid. Denna algoritm uppstår från två nya resultat: en deterministisk O(log n)-tid LLL algoritm för trädstrukturerade instanser, och en randomiserad O(log log n)-tid graf splittrande metod för att bryta beroende grafen i oberoende O(log n)-storlek LLL fall. • En naturlig metod för att datorisera ( till + 1)-kant färgläggningar (Vizing's theorem) är att förlänga partiella färgningar genom iterativt omfärgning delar av grafen, t.ex., via "augmenting banor." Vi bevisar att detta tillvägagångssätt kan vara livsdugligt, men i värsta fall kräver omfärgning subgrafer av diametern  och/eller log n. Detta står i kontrast till distribuerade algoritmer för Brooks' teorem [34], som utnyttjar existensen av O (log  på n) längd förstärkningsvägar.
Vi hänvisar också till REF för en mer detaljerad undersökning av randomiserade kantfärgsalgoritmer.
The Complexity of Distributed Edge Coloring with Small Palettes
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}