TIME-RELAXED 1-FAULT TOLERANT BROADCAST NETWORKS
Abstract
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.
References
- Networks 27, 293 (1996). Crossref, ISI, Google Scholar
- Networks 26, 125 (1995), DOI: 10.1002/net.3230260302. Crossref, ISI, Google Scholar
- Discrete Applied Mathematics 36, 97 (1992), DOI: 10.1016/0166-218X(92)90226-Z. Crossref, ISI, Google Scholar
- Discrete Applied Mathematics 93, 205 (1999), DOI: 10.1016/S0166-218X(99)00043-8. Crossref, ISI, Google Scholar
- Parallel Processing Letters 9, 53 (1999), DOI: 10.1142/S0129626499000086. Link, ISI, Google Scholar
- Networks 9, 313 (1979), DOI: 10.1002/net.3230090404. Crossref, ISI, Google Scholar
- Discrete Mathematics 25, 189 (1979), DOI: 10.1016/0012-365X(79)90022-0. Crossref, ISI, Google Scholar
- Networks 22, 469 (1992), DOI: 10.1002/net.3230220505. Crossref, ISI, Google Scholar
- Discrete Applied Mathematics 53, 135 (1994), DOI: 10.1016/0166-218X(94)90181-3. Crossref, ISI, Google Scholar
- Networks 19, 637 (1989), DOI: 10.1002/net.3230190606. ISI, Google Scholar
L. H. Khachatrian and H. S. Haroutunian , On Optimal Broadcast Graphs, Proceedings of the Fourth International Colloquium on Coding Theory (1991) pp. 65–72. Google Scholar- Networks 15, 159 (1985), DOI: 10.1002/net.3230150203. Crossref, ISI, Google Scholar
- Asia-Pacific Journal of Operational Research 24, 687 (2007), DOI: 10.1142/S0217595907001450. Link, ISI, Google Scholar
-
L. Schrage , User's Manual for LINGO ( Lingo Systems Inc. , Chicago, IL , 1991 ) . Google Scholar - Discrete Applied Mathematics 25, 263 (1998). Google Scholar
- SIAM Journal on Computing 10, 692 (1981), DOI: 10.1137/0210052. Crossref, ISI, Google Scholar
- J. A. Ventura, B. Q. Rieksts, R. G. McGarvey, and N. Ahn, 0-1 Linear Programming Models for High-Performance Minimum-Cost Broadcasting in Communication Networks, Working Paper, Department of Industrial and Manufacturing Engineering, Pennsylvania State University, University Park, PA, 2004 . Google Scholar
- Telecommunication Systems 3, 259 (1995), DOI: 10.1007/BF02110308. Crossref, ISI, Google Scholar


