Time-relaxed 1-fault tolerant broadcast networks

In a 1-fault tolerant minimal broadcast network, a node of a network, called the originator, has a message which is to be transmitted to all other nodes of the network in minimum time regardless of the failure of a single communication line. In some instances, it is advantageous to use time-relaxed broadcast networks that require slightly more than the minimum transmission time, but have sparser edge sets. This paper presents a general compounding algorithm to construct sparse, time-relaxed, 1-fault tolerant broadcast networks. In the algorithm, copies of a broadcast network without faults are interconnected with additional edges according to the structure of a 1-fault tolerant broadcast network with two special properties. Both the 1-fault tolerant broadcast network and the broadcast network without faults may be time-relaxed. Computational results show that the algorithm yields sparser networks by allowing additional time units.