Title: Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth
Abstract: 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Δ5logn) for arbitrary constants d,ε 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 $\Delta \in \Omega(\log^{1+1/\log^* n} n)$ and $\chi\in O(\Delta/\log^{1+1/\log^* n} n)$ then our algorithm executes in time O(logχ + 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 \Delta+\sqrt{\log n})$ . The algorithm works without knowledge of χ and uses less than Δ colors, i.e., (1 − 1/O(χ))Δ with high probability. To the best of our knowledge this is the first distributed algorithm for (such) general graphs taking the chromatic number χ into account.
Publication Year: 2011
Publication Date: 2011-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 18
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot