Multiple message broadcasting in communication networks. (English) Zbl 0856.90048
Summary: Broadcasting refers to the process of dissemination of a set of messages originating from one node to all other nodes in a communication network. We assume that, at any given time, a node can transmit a message along at most one incident link and simultaneously receive a message along at most one incident link. We first present an algorithm for determining the amount of time needed to broadcast \(k\) messages in an arbitrary tree. Second, we show that, for every \(n\), there exists a graph with \(n\) nodes whose \(k\)-message broadcast time matches the trivial lower bound \(\lceil\log n\rceil+ k- 1\) by designing a broadcast scheme for complete graphs. We call those graphs minimal broadcast graphs. Finally, we construct an \(n\) node minimal broadcast graph with fewer than \((\lceil\log n\rceil+ 1) 2^{\lceil\log n\rceil- 1}\) edges.
MSC:
| 90B18 | Communication networks in operations research |
References:
| [1] | and , Broadcasting multiple messages in simultaneous send/receive systems. Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing (1991) 344–347. |
| [2] | and , Optimal multiple message broadcasting in telephone-like communication systems. Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing (1994) 216–223. |
| [3] | and , Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Englewood Cliffs, NJ (1989). · Zbl 0743.65107 |
| [4] | Chau, J Combin. Info. Syst. Sci. 10 pp 110– (1985) |
| [5] | and , Multiple-message broadcasting in complete graphs. Proceedings of the 10th SE Conference on Combinatorics. Graph Theory and Computing. Utilitas Mathematica, Winnipeg (1979) 251–260. |
| [6] | and , Optimal multi-message broadcasting in complete graphs. Proceedings of the 11th SE Conference on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg (1980) 181–199. · Zbl 0456.05057 |
| [7] | Farley, SIAM J. Appl. Math. 39 pp 385– (1980) |
| [8] | Farley, Networks 9 pp 313– (1979) |
| [9] | Farley, Discr. Math. 25 pp 189– (1979) |
| [10] | and , Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979). · Zbl 0411.68039 |
| [11] | Gargano, Networks 19 pp 673– (1989) |
| [12] | Grigni, SIAM J. Disc. Math. 4 pp 207– (1991) |
| [13] | Hedetniemi, Networks 18 pp 319– (1988) |
| [14] | Ho, J. Parallel Distrib. Comput. 13 pp 246– (1991) |
| [15] | Johnsson, IEEE Tr. Comput. C-38 pp 1249– (1989) |
| [16] | , and , Optimal broadcast and summation in the LogP model. Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures (1993) 142–153. |
| [17] | Koh, IEEE Tr. Comput. C-40 pp 1174– (1991) |
| [18] | Koh, Networks 23 pp 71– (1993) |
| [19] | Proskurowski, IEEE Tr. Comput. C-30 pp 363– (1981) |
| [20] | Slater, SIAM J. Comput. 10 pp 692– (1981) |
| [21] | Ventura, Networks 23 pp 481– (1993) |
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.
