Toward optimal broadcast in a star graph using multiple spanning trees

Yu-Chee Tseng*, Jang Ping Sheu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


In a multicomputer network, sending a packet typically incurs two costs: start-up time and transmission time. This work is motivated by the observation that most broadcast algorithms in the literature for the star graph networks only try to minimize one of the costs. Thus, many algorithms, though claimed to be optimal, are only so when one of the costs is negligible. In this paper, we try to optimize both costs simultaneously for four types of broadcast problems: one-to-all or all-to-all broadcasting in an n-star network with either one-port or all-port communication capability. As opposed to earlier solutions, the main technique used in this paper is to construct from a source node multiple spanning trees, along each of which one partition of the broadcast message is transmitted.

Original languageEnglish
Pages (from-to)593-599
Number of pages7
JournalIEEE Transactions on Computers
Issue number5
StatePublished - 1 Dec 1997


  • All-to-all broadcast
  • Collective communication
  • Multi-computer networks
  • One-to-all broadcast
  • Parallel architecture
  • Routing
  • Star graph

Fingerprint Dive into the research topics of 'Toward optimal broadcast in a star graph using multiple spanning trees'. Together they form a unique fingerprint.

Cite this