Multi-channel assignment for communication in radio networks

Dariusz R. Kowalski, Mariusz A. Rokicki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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 Ω(logn)-inapproximable, unless NP ⊂ DTIME(nlog 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.

Original languageEnglish (US)
Title of host publicationTheory and Practice of Algorithms in (Computer) Systems - First International ICST Conference, TAPAS 2011, Proceedings
Number of pages12
StatePublished - 2011
Externally publishedYes
Event1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011 - Rome, Italy
Duration: Apr 18 2011Apr 20 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6595 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Multi-channel assignment for communication in radio networks'. Together they form a unique fingerprint.

Cite this