TY - GEN
T1 - Multi-channel assignment for communication in radio networks
AU - Kowalski, Dariusz R.
AU - Rokicki, Mariusz A.
N1 - Funding Information:
★ This work was supported by the Engineering and Physical Sciences Research Council [grant numbers EP/G023018/1, EP/H018816/1].
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79953825777&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79953825777&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-19754-3_19
DO - 10.1007/978-3-642-19754-3_19
M3 - Conference contribution
AN - SCOPUS:79953825777
SN - 9783642197536
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 181
EP - 192
BT - Theory and Practice of Algorithms in (Computer) Systems - First International ICST Conference, TAPAS 2011, Proceedings
T2 - 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011
Y2 - 18 April 2011 through 20 April 2011
ER -