Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth

摘要

We deterministically compute a Δ + 1 coloring in time O(Δ_(5c+2)· (Δ5)~(2/c)/(Δ_1)~∈ + (Δ_1)~∈+ log~* n) and O(Δ_(5c+2) · (Δ5)~(1/c)/Δ~∈+ Δ~∈+ (Δ_5)~d log Δ5 log n) for arbitrary constants d, t and arbitrary constant integer c, where Δ_i is defined as the maximal number of nodes within distance i for a node and Δ := Δ_1. Our greedy algorithm improves the state-of-the-art Δ + 1 coloring algorithms for a large class of graphs, e.g. graphs of moderate neighborhood growth. We also state and analyze a randomized coloring algorithm in terms of the chromatic number, the run time and the used colors. If Δ ∈ Ω(log~(1+1/log~*n)n) and Χ ∈ O(Δ/log~(1+1/log~*n) n) then our algorithm executes in time O(log x + log~* n) with high probability. For graphs of polylogarithmic chromatic number the analysis reveals an exponential gap compared to the fastest Δ + 1 coloring algorithm running in time O(log Δ + log n~(1/2)). The algorithm works without knowledge of x and uses less than Δ colors, i.e., (1 - 1/O(x))Δ with high probability. To the best of our knowledge this is the first distributed algorithm for (such) general graphs taking the chromatic number x into account.