Construction of time-relaxed minimal broadcast networks

Michael J. Dinneen, Jose A. Ventura, Mark C. Wilson, Golbon Zakeri

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


In broadcasting, or one-to-all communication, a message originally held in one node of the network must be transmitted to all the other nodes. A minimal broadcast network is a communication network that can transmit a message originated at any node to all other nodes of the network in minimum time. In this paper, we present a compound method to construct sparse, time-relaxed, minimal broadcast networks (t-mbn), in which broadcasting can be accomplished in slightly more than the minimum time. The proposed method generates a new network by connecting a subset of nodes from several copies of a t1-mbn using the structure of another t2-mbn. The objective is to construct a network as sparse as possible satisfying the desired broadcasting time constraint. Computational results illustrate the effectiveness of the proposed method.

Original languageEnglish (US)
Pages (from-to)53-68
Number of pages16
JournalParallel Processing Letters
Issue number1
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Construction of time-relaxed minimal broadcast networks'. Together they form a unique fingerprint.

Cite this