Bounded-call broadcasting. (English) Zbl 0807.94036
Summary: In this paper, we initiate the study of broadcasting under operational protocols that bound the number of calls made by any site to be less than or equal to a predetermined constant, \(c\). Specifically, we (i) investigate the \(c\)-call broadcast time function, being the minimum possible time required to inform all vertices in a network when the number of calls made by each site is bounded by \(c\); (ii) define a general class of sparse minimum-time \(c\)-call broadcast graphs and an associated broadcast protocol; (iii) characterize the structure of minimum broadcast trees with call bound \(c\); (iv) discuss the complexity of the recognition problem for minimum-time \(c\)-call broadcast graphs, and (v) present a catalog of minimum 2-call broadcast graphs for small values of \(n\).
MSC:
| 94C15 | Applications of graph theory to circuits and networks |
| 90B18 | Communication networks in operations research |
| 05C90 | Applications of graph theory |
References:
| [1] | Bermond, J.-C.; Hell, P.; Liestman, A. L.; Peters, J. G., Sparse broadcast graphs, Discrete Appl. Math., 36, 97-130 (1992) · Zbl 0764.05042 |
| [2] | J.-C. Bermond, P. Hell, A.L. Liestman and J.G. Peters, Broadcasting in bounded degree graphs, SIAM J. Discrete Math., to appear.; J.-C. Bermond, P. Hell, A.L. Liestman and J.G. Peters, Broadcasting in bounded degree graphs, SIAM J. Discrete Math., to appear. · Zbl 0753.68007 |
| [3] | Bermond, J.-C.; Peyrat, C., Broadcasting in DeBruijn networks, Proceedings of the 19th South-Eastern Conference on Combinatorics, Graph Theory and Computing. Proceedings of the 19th South-Eastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 283-292 (1988) · Zbl 0673.94027 |
| [4] | Brown; Sedgewick, A dichromatic framework for balanced trees, Proceedings 19th STOC, 8-21 (1978) |
| [5] | chau, S. C.; Liestman, A. L., Constructing minimal broadcast networks, J. Combin. Inform. System Sci., 10, 110-122 (1985) · Zbl 0696.90077 |
| [6] | Chung, F. R.K., Diameters of graphs: old problmes and new results, Proceedings of the 18th South-Eastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 295-317 (1987) · Zbl 0695.05029 |
| [7] | Garey; Johnson, Computers and Intractability (1978), Freeman: Freeman New York |
| [8] | Gargano, L.; Vaccaro, U., On the construction of minimal broadcast networks, Networks, 19, 673-689 (1989) · Zbl 0676.90021 |
| [9] | Grigni, M.; Peleg, D., Tight bounds on minimum broadcast networks, TR MIT/LCS/TM-374 (1988) |
| [10] | Farley, A. M., Minimal broadcast networks, Networks, 9, 313-332 (1979) · Zbl 0425.94025 |
| [11] | Farley, A. M.; Hedetniemi, S. T.; Mitchell, S. L.; Proskurowski, A., Minimum broadcast graphs, Discrete Math., 25, 189-193 (1979) · Zbl 0404.05038 |
| [12] | Liestman, A. L.; Peters, J. G., Broadcast networks of bounded degree, SIAM J. Discrete Math., 1, 531-540 (1988) · Zbl 0662.94027 |
| [13] | Mitchell, S. L.; Hedetniemi, S. T., A census of minimum broadcast graphs, J. Combin. Inform. System Sci., 5, 141-151 (1980) · Zbl 0449.05034 |
| [14] | Proskurowski, A., Minimum broadcast trees, IEEE Trans. Comput., C-30, 5, 363-366 (1981) |
| [15] | Slater, P. J.; Cockayne, E.; Hedetniemi, S. T., Information dissemination in trees, SIAM J. Comput., 10, 692-701 (1981) · Zbl 0468.68064 |
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.
