Fan Zhang, Junwei Cao, et al.
IEEE TETC
We deterministically compute a Δ+1 coloring and a maximal independent set(MIS) in time O(Δ1/2+Θ(1/√h)+logn) for Δ1+i≤Δ1+i/h, where Δj is defined as the maximal number of nodes within distance j for a node and Δ:=Δ1. Our greedy coloring and MIS algorithms improve the state-of-the-art algorithms running in O(Δ+logn) for a large class of graphs, i.e., graphs of (moderate) neighborhood growth with h≥36. We also state and analyze a randomized coloring algorithm in terms of the chromatic number, the run time and the used colors. Our algorithm runs in time O(logχ+logn) for Δ∈Ω(log1+1/lognn) and χ∈O(Δ/log1+1/log*nn). 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). 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. We also improve on the state of the art deterministic computation of (2,c)-ruling sets. © 2012 Elsevier B.V. All rights reserved.
Fan Zhang, Junwei Cao, et al.
IEEE TETC
Victor Valls, Panagiotis Promponas, et al.
IEEE Communications Magazine
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Pradip Bose
VTS 1998