Deterministic communication in radio networks with large labels

Leszek Gąsieniec, Aris Pagourtzis, Igor Potapov

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

11 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
EditorsRolf Möhring, Rajeev Raman
PublisherSpringer Verlag
Number of pages13
ISBN (Electronic)3540441808, 9783540441809
StatePublished - 2002
Externally publishedYes
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

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


Conference10th Annual European Symposium on Algorithms, ESA 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Deterministic communication in radio networks with large labels'. Together they form a unique fingerprint.

Cite this