Failure diagnosis with incomplete information in cable networks
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006
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.
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Zohar Feldman, Avishai Mandelbaum
WSC 2010
B.K. Boguraev, Mary S. Neff
HICSS 2000