An efficient algorithm for constructing delay bounded minimum cost multicast trees

Shu Li, Kami Melhem, Taieb Znati

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


Multimedia applications are usually resource intensive, have stringent quality of service requirements, and in many cases involve large groups of participants. Multicasting is poised to play an important role in future deployment of these applications. This paper focuses on developing delay-bounded, minimum-cost multicast trees, linking a source to a set of multicast destination nodes. The approach taken in this paper is efficient, flexible and unique in the sense that it cleverly limits its computation only to paths that originate at multicast nodes, thereby avoiding computing paths that exclusively link non-multicast nodes. The simulation results show that the multicast trees produced by the proposed heuristic are of lower cost than those produced by other well-known heuristics, including those which use an expensive k-shortest-paths procedure to minimize the cost of the multicast tree. Furthermore, the results show that, in comparison to other heuristics, the proposed scheme results in a significant reduction in the computation time required to build the multicast tree.

Original languageEnglish
Pages (from-to)1399-1413
Number of pages15
JournalJournal of Parallel and Distributed Computing
Issue number12
Publication statusPublished - Dec 2004
Externally publishedYes


  • Bounded delays
  • Constrained minimization
  • Dijkstra's algorithm
  • Discrete delays
  • Low-cost multicasting
  • Multicast trees

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'An efficient algorithm for constructing delay bounded minimum cost multicast trees'. Together they form a unique fingerprint.

Cite this