Construction of Time-Relaxed c-Broadcast Networks

Shiwoo Lee, Jose A. Ventura

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


C-broadcasting is an information dissemination task where a message, originated at any node in a network, is transmitted to all other nodes with the restriction that each node having the message can transmit it to almost c neighbors simultaneously. If the transmission time of the message is set to be one time unit, a minimal c-broadcast network (c-MBN) is a communication network in which c-broadcasting from any node can be accomplished in [logc+1 n] time untis where n is the number of nodes and [logc+1 n] is the fastest possible broadcast time. If networks are sparse, additional time units may be required to perform c-broadcasting. A time-relaxed c-broadcast network, denoted as (t, c)-RBN, is a network where c-broadcasting from any node can be completed in [logc+1 n]+t time units. In this paper, a network compounding algorithm is proposed to construct large sparse (t, c)-RBNs by linking multiple copies of a time-relaxed network of small size using the structure of another time-relaxed network. Computational results are presented to show the effectiveness of the proposed algorithm.

Original languageEnglish (US)
Pages (from-to)47-59
Number of pages13
JournalTelecommunication Systems
Issue number1
StatePublished - Sep 1 2003

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'Construction of Time-Relaxed c-Broadcast Networks'. Together they form a unique fingerprint.

Cite this