Binary linear programming models for robust broadcasting in communication networks. (English) Zbl 1333.05275
Summary: Broadcasting is an information dissemination process in communication networks whereby a message, originated at any node of a network, is transmitted to all other nodes of the network. In \(c\)-broadcasting, each node having the message completes up to \(c\) transmissions to its neighbors over the communication lines in one time unit. In a \(k\)-fault tolerant \(c\)-broadcast network, the broadcasting process can be accomplished even if \(k\) communication lines fail. This paper presents innovative binary linear programming formulations to construct \(c\)-broadcast graphs, \(k\)-fault-tolerant \(c\)-broadcast graphs, and their time-relaxed versions. The proposed mathematical models are used to generate eight previously unknown minimum \(c\)-broadcast graphs, new upper bounds for eleven other instances of the \(c\)-broadcast problem, and over 30 minimum \(k\)-fault-tolerant \(c\)-broadcast graphs. The paper also provides a construction method to produce an upper bound for an infinite family of \(k\)-fault-tolerant \(c\)-broadcast graphs.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C35 | Extremal problems in graph theory |
| 05C90 | Applications of graph theory |
References:
| [1] | Ahlswede, R.; Gargano, L.; Haroutunian, H. S.; Khachatrian, L. H., Fault-tolerant minimum broadcast networks, Networks, 27, 293-307 (1996) · Zbl 0865.90046 |
| [3] | Averbuch, A.; Rodity, Y.; Shoham, B., Construction of minimum time-relaxed broadcasting communication networks, J. Combin. Math. Combin. Comput., 43, 123-134 (2002) · Zbl 1027.90010 |
| [4] | Averbuch, A.; Shabtai, R.; Roditty, Y., Efficient construction of broadcast graphs, Discrete Appl. Math., 171, 9-14 (2014) · Zbl 1288.05133 |
| [5] | Barsky, G.; Grigoryan, H.; Harutyunyan, H., Tight lower bounds on broadcast function for \(n = 24\) and 25, Discrete Appl. Math., 175, 109-114 (2014) · Zbl 1298.05291 |
| [6] | Bermond, J. C.; Delorme, C.; Quisquater, J. J., Strategies for interconnection networks: Some methods from graph theory, J. Parallel Distrib. Comput., 3, 433-449 (1986) |
| [7] | Bermond, J. C.; Fraigniaud, P.; Peters, J. G., Antepenultimate broadcasting, Networks, 26, 125-137 (1995) · Zbl 0856.90046 |
| [8] | Bermond, J. C.; Hell, P.; Liestman, A.; Peters, J. G., Sparse broadcast graphs, Discrete Appl. Math., 36, 97-130 (1992) · Zbl 0764.05042 |
| [9] | Dekker, A., Applying social network concepts to military C4ISR Architecture, Connections, 24, 3, 93-103 (2002) |
| [10] | Dekker, A., Centralisation and decentralisation in network centric warfare, J. Battlefield Technol., 6, 2, 23-28 (2003) |
| [11] | Dinneen, M. J.; Ventura, J. A.; Wilson, M. C.; Zakeri, G., Compound constructions of minimal broadcast networks, Discrete Appl. Math., 93, 205-232 (1999) · Zbl 0941.90009 |
| [12] | Dinneen, M. J.; Ventura, J. A.; Wilson, M. C.; Zakeri, G., Construction of time-relaxed minimal broadcast networks, Paral. Proc. Lett., 9, 1, 53-68 (1999) |
| [13] | Farley, A., Minimum broadcast networks, Networks, 9, 313-332 (1979) · Zbl 0425.94025 |
| [14] | Farley, A. M.; Hedetniemi, S. T.; Mitchell, S.; Proskurowski, A., Minimal broadcast graphs, Discrete Math., 25, 189-193 (1979) · Zbl 0404.05038 |
| [15] | Farley, A. M.; Proskurowski, A., Between whispering and shouting, Congr. Numer., 72, 209-212 (1990) |
| [16] | Farley, A. M.; Proskurowski, A., Bounded-call broadcasting, Discrete Appl. Math., 53, 37-53 (1994) · Zbl 0807.94036 |
| [17] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [18] | Gargano, L., Tighter bounds on fault-tolerant broadcasting and gossiping, Networks, 22, 469-486 (1992) · Zbl 0758.90033 |
| [19] | Gargano, L.; Vaccaro, U., On the construction of minimal broadcast networks, Networks, 19, 637-689 (1989) · Zbl 0676.90021 |
| [20] | Gargano, L.; Vaccaro, U., Minimum time broadcast networks tolerating a logarithmic number of faults, SIAM J. Discrete Math., 5, 178-198 (1992) · Zbl 0751.94014 |
| [21] | Grigni, M.; Peleg, D., Tight bounds on minimum broadcast networks, SIAM J. Discrete Math., 4, 2, 207-222 (1991) · Zbl 0725.94016 |
| [22] | Grigoryan, H.; Harutyunyan, H., New lower bounds on broadcast function, Lecture Notes in Comput. Sci., 8546, 174-184 (2014) · Zbl 1359.05116 |
| [23] | Harutyunyan, H., An efficient vertex addition method for broadcast networks, Internet Math., 5, 3, 211-225 (2009) · Zbl 1184.68033 |
| [24] | Harutyunyan, H.; Liestman, A., More broadcast graphs, Discrete Appl. Math., 98, 1-2, 81-102 (1999) · Zbl 0936.05059 |
| [25] | Harutyunyan, H.; Liestman, A., Improved upper and lower bounds for \(k\)-broadcasting, Networks, 37, 2, 94-101 (2001) · Zbl 0971.05059 |
| [26] | Harutyunyan, H.; Liestman, A., \(k\)-broadcasting in trees, Networks, 38, 3, 163-168 (2001) · Zbl 0985.94063 |
| [27] | Harutyunyan, H.; Liestman, A., On the monotonicity of the broadcast function, Discrete Math., 262, 149-157 (2003) · Zbl 1032.90055 |
| [28] | Harutyunyan, H.; Liestman, A., Upper bounds on the broadcast function using minimum dominating sets, Discrete Math., 312, 20, 2992-2996 (2012) · Zbl 1252.05161 |
| [29] | Harutyunyan, H.; Liestman, A.; Peters, J.; Richards, D., Broadcasting and gossiping, (Gross, J.; Yellen, J.; Zhang, P., The Handbook of Graph Theory (2013), Chapman and Hall/CRC), 1477-1494 |
| [30] | Hedetniemi, S. M.; Hedetniemi, S. T.; Liestman, A., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047 |
| [31] | Hromkovic, J.; Klasing, R.; Pelc, A.; Ruzicka, P.; Unger, W., (Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance, Texts Theoretical Computer Science. EATCS Series (2005), Springer: Springer Berlin) · Zbl 1067.68016 |
| [33] | Konig, J. C.; Lazard, E., Minimum \(k\)-broadcast graphs, Discrete Appl. Math., 53, 199-209 (1994) · Zbl 0807.94030 |
| [34] | Lazard, E., Broadcasting in DMA-bound bounded degree graphs, Discrete Appl. Math., 37-38, 387-400 (1992) · Zbl 0755.94018 |
| [36] | Lee, S.; Ventura, J. A., An algorithm for constructing minimal c-broadcast networks, Networks, 38, 6-21 (2001) · Zbl 0984.68007 |
| [37] | Lee, S.; Ventura, J. A., Construction of time-relaxed \(c\)-broadcast networks, Telecommun. Syst., 24, 1, 47-59 (2003) |
| [38] | Liestman, A., Fault-tolerant broadcast graphs, Networks, 15, 159-171 (1985) · Zbl 0579.94030 |
| [39] | Liestman, A.; Peters, J., Broadcast networks of bounded degree, SIAM J. Discrete Math., 1, 531-540 (1988) · Zbl 0662.94027 |
| [40] | Pelc, A., Fault-tolerant broadcasting and gossiping in communication networks, Networks, 28, 143-156 (1996) · Zbl 0865.90058 |
| [41] | Peleg, D.; Schäffer, A., Time bounds on fault-tolerant broadcasting, Networks, 19, 803-822 (1989) · Zbl 0682.90045 |
| [42] | Richards, D.; Liestman, A., Generalizations of broadcasting and gossiping, Networks, 18, 125-138 (1988) · Zbl 0709.90540 |
| [43] | Shao, B., On \(k\)-broadcasting in graphs (2006), Concordia University, Montreal: Concordia University, Montreal PQ, Canada, (Ph.D. thesis) |
| [44] | Shastri, A., Time-relaxed broadcasting in communication networks, Discrete Appl. Math., 83, 263-278 (1998) · Zbl 0917.90122 |
| [45] | Slater, P. J.; Cockayne, E. J.; Hedetniemi, S. T., Information dissemination in trees, SIAM J. Comput., 10, 692-701 (1981) · Zbl 0468.68064 |
| [46] | Weng, M. X.; Ventura, J. A., A doubling procedure for constructing minimal broadcast networks, Telecommun. Syst., 3, 259-293 (1995) |
| [47] | Yao, T.; Che Bor Lam, P.; Lin, W.; Zhou, G., On time-relaxed broadcasting networks, Discrete Appl. Math., 158, 1029-1034 (2010) · Zbl 1210.05168 |
| [48] | Yao, T.; Zhou, G.; Zhou, J., A 1-relaxed minimum broadcast graph on 15 vertices, Appl. Math. Lett., 17, 249-252 (2004) · Zbl 1087.90014 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
