TY - GEN
T1 - Deterministic communication in radio networks with large labels
AU - Gąsieniec, Leszek
AU - Pagourtzis, Aris
AU - Potapov, Igor
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - We study deterministic gossiping in ad-hoc radio networks, where labels of the nodes are large, i.e., they are polynomially large in the size n of the network. A label-free model was introduced in the context of randomized broadcasting in ad-hoc radio networks, see [2]. Most of the work on deterministic communication in ad-hoc networks was done for the model with labels of size O(n), with few exceptions; Peleg [19] raised the problem of deterministic communication in ad-hoc radio networks with large labels and proposed the first deterministic O(n2 logn)-time broadcasting algorithm. In [11] Chrobak et al. proved that deterministic radio broadcasting can be performed in time O(n log2 n); their result holds for large labels. Here we propose two new deterministic gossiping algorithms for ad-hoc radio networks with large labels. In particular: - a communication procedure giving an O(n5/3 log3 n)-time deterministic gossiping algorithm for directed networks and an O(n4/3 log3 n)-time algorithm for undirected networks; -a gossiping procedure designed particularly for undirected networks resulting in an almost linear O(n log3 n)-time algorithm.
AB - We study deterministic gossiping in ad-hoc radio networks, where labels of the nodes are large, i.e., they are polynomially large in the size n of the network. A label-free model was introduced in the context of randomized broadcasting in ad-hoc radio networks, see [2]. Most of the work on deterministic communication in ad-hoc networks was done for the model with labels of size O(n), with few exceptions; Peleg [19] raised the problem of deterministic communication in ad-hoc radio networks with large labels and proposed the first deterministic O(n2 logn)-time broadcasting algorithm. In [11] Chrobak et al. proved that deterministic radio broadcasting can be performed in time O(n log2 n); their result holds for large labels. Here we propose two new deterministic gossiping algorithms for ad-hoc radio networks with large labels. In particular: - a communication procedure giving an O(n5/3 log3 n)-time deterministic gossiping algorithm for directed networks and an O(n4/3 log3 n)-time algorithm for undirected networks; -a gossiping procedure designed particularly for undirected networks resulting in an almost linear O(n log3 n)-time algorithm.
UR - http://www.scopus.com/inward/record.url?scp=84938083217&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84938083217&partnerID=8YFLogxK
U2 - 10.1007/3-540-45749-6_46
DO - 10.1007/3-540-45749-6_46
M3 - Conference contribution
AN - SCOPUS:84938083217
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 512
EP - 524
BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
A2 - Möhring, Rolf
A2 - Raman, Rajeev
PB - Springer Verlag
T2 - 10th Annual European Symposium on Algorithms, ESA 2002
Y2 - 17 September 2002 through 21 September 2002
ER -