id: 05037291
dt: j
an: 05037291
au: Elsässer, R.; G\c asieniec, L.
ti: Radio communication in random graphs.
so: J. Comput. Syst. Sci. 72, No. 3, 490-506 (2006).
py: 2006
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: radio broadcasting; random graphs
ci: 
li: doi:10.1016/j.jcss.2005.09.003
ab: Summary: One of the most frequently studied problems in the context of
    information dissemination in communication networks is the broadcasting
    problem. We propose here several time efficient, centralized as well as
    fully distributed procedures for the broadcasting problem in random
    radio networks. In particular, we show how to perform a centralized
    broadcast in a random graph $G_p=(V,E)$ of size $n=|V|$ and expected
    average degree $d=pn$ in time $O(\ln n/\ln d)$. Later we present a
    randomized distributed broadcasting algorithm with the running time
    $O(\ln n)$ source. In both cases we show that the presented algorithms
    are asymptotically optimal by deriving lower bounds on the complexity
    of radio broadcasting in random graphs. In these proofs we determine
    some structural properties of random graphs and develop new techniques
    which might be useful for further research in this field. We should
    note here that the results of this paper hold with probability
    $1-o(1/n)$.
rv: