Deterministic M2M multicast in radio networks

Leszek Gasieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


We study the problem of exchanging messages within a fixed group of k nodes, called participants, in an n-node radio network, modeled as an undirected graph. This communication task was previously considered in the setting of ATM video applications, in [J.M. Tsai, H.-H. Fang, C.-Y. Lee, A multicast solution for ATM video applications, IEEE Trans. Circuits Systems Video Technol. 7 (1997) 675-686], and was called multipoint-to-multipoint (M2M) multicasting. While the radio network topology is known to all nodes, it is assumed that no node is aware of the location of the participants. We give a distributed deterministic algorithm for the M2M multicasting problem in radio networks, and analyze its time complexity. We show that if the maximum distance between any two out of k participants is d then this local information exchange problem can be solved in time O (d log2 n + k log4 n).

Original languageEnglish (US)
Pages (from-to)196-206
Number of pages11
JournalTheoretical Computer Science
Issue number1-3
StatePublished - Oct 11 2006
Externally publishedYes


  • Broadcasting
  • Deterministic algorithm
  • Multicasting
  • Radio communication

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Deterministic M2M multicast in radio networks'. Together they form a unique fingerprint.

Cite this