05887550

a

05887550 Kowalski, Dariusz R. Rokicki, Mariusz A. Multi-channel assignment for communication in radio networks. 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). 2011 Berlin: Springer EN

doi:10.1007/978-3-642-19754-3_19

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 $\Omega (\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(\Delta + \ln ^{2} n)$ channels for connectivity and at most $\Delta $ channels for one-receiver problem, where $n$ is the number of nodes and $\Delta $ 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.