Approximation Schemes for Broadcasting in Heterogenous Networks

Samir Khuller*, Yoo Ah Kim, Gerhard Woeginger

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor pi has transmission time ti, which is the time taken to send a message to any other processor in the cluster. Previously, it was shown that the Fastest Node First method (FNF) gives a 1.5 approximate solution. In this paper we show that there is a polynomial time approximation scheme for the problems of broadcasting and multicasting in such a heterogenous cluster.

Original languageEnglish (US)
Pages (from-to)163-170
Number of pages8
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - Dec 1 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Approximation Schemes for Broadcasting in Heterogenous Networks'. Together they form a unique fingerprint.

Cite this