id: 05887550
dt: a
an: 05887550
au: Kowalski, Dariusz R.; Rokicki, Mariusz A.
ti: Multi-channel assignment for communication in radio networks.
so: Marchetti-Spaccamela, Alberto (ed.) et al., Theory and practice of
    algorithms in (computer) systems. First international ICST conference,
    TAPAS 2011, Rome, Italy, April 18‒20, 2011. Proceedings. Berlin:
    Springer (ISBN 978-3-642-19753-6/pbk). Lecture Notes in Computer
    Science 6595, 181-192 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-19754-3_19
ab: Summary: We study three communication primitives in wireless radio
    networks: Connectivity, One-Receiver, and Gossiping. Radio networks are
    modeled by undirected graphs of general topology. We consider
    centralized solutions to the abovementioned problems. In Connectivity
    and One-Receiver problems, we study the impact of multi-channel
    assignment to the hardness and approximation of computing of
    assignments with the minimum number of channels. More precisely, we
    show that both Connectivity and One-Reciver are $Ω(\log
    n)$-inapproximable, unless $\text{{\it NP}} \subset \text{{\sc Dtime}}
    (n^{\log\log n})$. We also give polynomial time algorithms computing
    multi-channel assignments using at most $3(Δ+ \ln ^{2} n)$ channels
    for connectivity and at most $Δ$ channels for one-receiver problem,
    where $n$ is the number of nodes and $Δ$ is the maximum node degree in
    the graph. Finally, in case of the classical gossiping problem, related
    to the connectivity problem, we show that it is NP-complete.
rv: