id: 05781472
dt: j
an: 05781472
au: Schneider, Johannes; Wattenhofer, Roger
ti: An optimal maximal independent set algorithm for bounded-independence
    graphs.
so: Distrib. Comput. 22, No. 5-6, 349-361 (2010).
py: 2010
pu: Springer-Verlag, Berlin
la: EN
cc: 
ut: ad hoc network; sensor network; radio network; unit disk graph; growth
    bounded graph; bounded-independence graph; local algorithm; parallel
    algorithm; maximal independent set; maximal matching; dominating set;
    connected dominating set; coloring; symmetry breaking
ci: 
li: doi:10.1007/s00446-010-0097-1
ab: Summary: We present a novel distributed algorithm for the maximal
    independent set problem. On bounded-independence graphs our
    deterministic algorithm finishes in $O(\log ^{\ast}n)$ time, $n$ being
    the number of nodes. In light of Linial’s $Ω(\log^{\ast} n)$ lower
    bound our algorithm is asymptotically optimal. Furthermore, it solves
    the connected dominating set problem for unit disk graphs in $O(\log
    ^{\ast} n)$ time, exponentially faster than the state-of-the-art
    algorithm. With a new extension our algorithm also computes a $δ+ 1$
    coloring and a maximal matching in $O(\log ^{\ast} n)$ time, where $δ$
    is the maximum degree of the graph.
rv: