Multicasting in heterogeneous networks

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

Research output: Contribution to journalConference articlepeer-review

47 Scopus citations

Abstract

In heterogeneous networks sending messages may incur different delays on different edges, and each processor may have a different switching time between messages. The well studied Telephone model is obtained when all edge 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 processors 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)448-453
Number of pages6
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Jan 1 1998
Externally publishedYes
EventProceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA
Duration: May 23 1998May 26 1998

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

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

Cite this