Access Restriction

Author Barenboim, Leonid ♦ Elkin, Michael
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Arboricity ♦ Arbdefective coloring ♦ Partial orientation
Abstract Consider an $\textit{n}-vertex$ graph $\textit{G}$ = $(\textit{V},$ $\textit{E})$ of maximum degree $\textit{Δ},$ and suppose that each vertex $\textit{v}$ ∈ $\textit{V}$ hosts a processor. The processors are allowed to communicate only with their neighbors in $\textit{G}.$ The communication is synchronous, that is, it proceeds in discrete rounds. In the distributed vertex coloring problem, the objective is to color $\textit{G}$ with $\textit{Δ}$ + 1, or slightly more than $\textit{Δ}$ + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time.) Efficient $\textit{randomized}$ algorithms for this problem are known for more than twenty years [Alon et al. 1986; Luby 1986]. Specifically, these algorithms produce a $(\textit{Δ}$ + 1)-coloring within $\textit{O}(log$ $\textit{n})$ time, with high probability. On the other hand, the best known $\textit{deterministic}$ algorithm that requires polylogarithmic time employs $O(Δ^{2})$ colors. This algorithm was devised in a seminal FOCS’87 paper by Linial [1987]. Its running time is $O(log^{*}$ $\textit{n}).$ In the same article, Linial asked whether one can color with significantly less than $Δ^{2}$ colors in deterministic polylogarithmic time. By now, this question of Linial became one of the most central long-standing open questions in this area. In this article, we answer this question in the affirmative, and devise a deterministic algorithm that employs $\textit{Δ}1+\textit{o}(1)$ colors, and runs in $\textit{polylogarithmic}$ time. Specifically, the running time of our algorithm is $\textit{O}(\textit{f}(\textit{Δ})log$ $\textit{Δ}$ log $\textit{n}),$ for an arbitrarily slow-growing function $\textit{f}(\textit{Δ})$ = $\textit{ω}(1).$ We can also produce an $\textit{O}(\textit{Δ}1+\textit{η})-coloring$ in $\textit{O}(log$ $\textit{Δ}$ log $\textit{n})-time,$ for an arbitrarily small constant $\textit{η}$ > 0, and an $\textit{O}(\textit{Δ})-coloring$ in $\textit{O}(\textit{Δε}$ log $\textit{n})$ time, for an arbitrarily small constant $\textit{ε}$ > 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity $\textit{a},$ our algorithm produces an $\textit{O}(\textit{a}1+\textit{η})-coloring,$ for an arbitrarily small constant $\textit{η}$ > 0, in time $\textit{O}(log$ $\textit{a}$ log $\textit{n}).$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2011-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 58
Issue Number 5
Page Count 25
Starting Page 1
Ending Page 25

Open content in new tab

   Open content in new tab
Source: ACM Digital Library