Message multicasting in heterogeneous networks

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

48 Scopus citations


In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone model by a factor of O(log n/log log k). No approximation algorithms were known for the general model considered in this paper.

Original languageEnglish (US)
Pages (from-to)347-358
Number of pages12
JournalSIAM Journal on Computing
Issue number2
StatePublished - 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


  • Approximation algorithms
  • Combinatorial optimization
  • Heterogeneous networks
  • LogP model
  • Multicast
  • Postal model


Dive into the research topics of 'Message multicasting in heterogeneous networks'. Together they form a unique fingerprint.

Cite this