Construction of Time-Relaxed c-Broadcast Networks

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 [log_c+1 n] time untis where n is the number of nodes and [log_c+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 [log_c+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.