William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
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.
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB