Minimum \(k\)-broadcast graphs. (English) Zbl 0807.94030
Summary: We study here a variant of broadcasting called \(k\)-broadcast, where a processor can call several of its neighbours in one time unit. A \(k\)- broadcast graph is an \(n\)-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time \(\lceil \log_{k + 1} n \rceil\). A minimum \(k\)-broadcast graph is a \(k\)- broadcast graph having the minimum number of edges. In this paper, after giving simple results generalizing previously known results on 1- broadcasting, we find minimum \(k\)-broadcast graphs for \(k + 3 \leq n \leq 2k + 3\).
MSC:
| 94C15 | Applications of graph theory to circuits and networks |
| 90B18 | Communication networks in operations research |
| 05C90 | Applications of graph theory |
References:
| [1] | J.C. Bermond, P. Hell, A.L. Liestman and J.G. Peters, New minimum broadcast graphs and sparse broadcast graphs, Discrete Appl. Math., to appear.; J.C. Bermond, P. Hell, A.L. Liestman and J.G. Peters, New minimum broadcast graphs and sparse broadcast graphs, Discrete Appl. Math., to appear. · Zbl 0764.05042 |
| [2] | Chau, S. C.; Liestman, A. L., Constructing minimal broadcast networks, J. Combin. Inform. Systems Sci., 10, 110-112 (1985) · Zbl 0696.90077 |
| [3] | Farley, A. M., Minimal broadcast networks, Networks, 9, 313-332 (1979) · Zbl 0425.94025 |
| [4] | Farley, A. M.; Hedetniemi, S.; Mitchell, S.; Proskurowski, A., Minimum broadcast graphs, Discrete Math., 25, 189-193 (1979) · Zbl 0404.05038 |
| [5] | Grigni, M.; Peleg, D., Tight bounds on minimum broadcast networks, SIAM J. Discrete Math., 4, 207-222 (1991) · Zbl 0725.94016 |
| [6] | Hedetniemi, S. M.; Hedetniemi, S. T.; Liestman, A. L., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1986) · Zbl 0649.90047 |
| [7] | Johnson, D.; Garey, M., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [8] | Lazard, E., Broadcasting in DMA-bound bounded degree graphs, Discrete Appl. Math., 37/38, 387-400 (1992) · Zbl 0755.94018 |
| [9] | Liestman, A. L.; Peters, J. G., Minimum broadcast digraphs (1989), Simon Fraser University: Simon Fraser University Burnaby, B.C, Tech. Rept. · Zbl 0755.94019 |
| [10] | Mitchell, S. L.; Hedetniemi, S. T., A census of minimum broadcast graphs, J. Combin. Inform. Systems Sci., 5, 141-151 (1980) · Zbl 0449.05034 |
| [11] | Mahéo, M.; Scalé, J.-F., Some minimum broadcast graphs, Discrete Appl. Math., 53, 275-285 (1994) · Zbl 0807.94028 |
| [12] | X. Wang, Manuscript (1986).; X. Wang, Manuscript (1986). |
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.
