×

Sparse broadcast graphs. (English) Zbl 0764.05042

Authors’ abstract: Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. Several previous papers have investigated ways to construct sparse graphs (networks) on an vertices in which this process can be completed in minimum time from any originator. In this paper, we describe four techniques to construct graphs of this type and show that they produce the sparsest known graphs for several values of \(n\). For \(n=18\), \(n=19\), \(n=30\) and \(n=31\) we also show that our new graphs are minimum broadcast graphs (i.e., that no graph with fewer edges is possible). These new graphs can be used with other techniques to improve the best known results for many larger values of \(n\).
Reviewer: S.Stahl (Lawrence)

MSC:

05C35 Extremal problems in graph theory
05C90 Applications of graph theory
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Alspach, Private communication, December, 1987; B. Alspach, Private communication, December, 1987
[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] Chau, S. C.; Liestman, A. L., Constructing minimal broadcast networks, J. Combin. Inform. System Sci., 10, 110-122 (1985) · Zbl 0696.90077
[4] Farley, A., Minimal broadcast networks, Networks, 9, 313-332 (1979) · Zbl 0425.94025
[5] Farley, A.; Hedetniemi, S.; Mitchell, S.; Proskurowski, A., Minimum broadcast graphs, Discrete Math., 25, 189-193 (1979) · Zbl 0404.05038
[6] Grigni, M.; Peleg, D., Tight bounds on minimum broadcast networks, SIAM J. Discrete Math., 4, 207-222 (1991) · Zbl 0725.94016
[7] Hedetniemi, S. T.; Hedetniemi, S. M.; Liestman, A. L., A survey of broadcasting and gossiping in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047
[8] Liestman, A. L.; Peters, J. G., Broadcast networks of bounded degree, SIAM J. Discrete Math., 1, 531-540 (1988) · Zbl 0662.94027
[9] Mitchell, S.; Hedetniemi, S., A census of minimum broadcast graphs, J. Combin. Inform. Systems Sci., 5, 141-151 (1980) · Zbl 0449.05034
[10] X. Wang, Manuscript (1986).; X. Wang, Manuscript (1986).
[11] Dineen, M. J.; Fellows, M. R.; Faber, V., Algebraic constructions of efficient broadcast networks, (Tech. Rept. DCS-153-IR (1991), University of Victoria: University of Victoria Victoria, B.C) · Zbl 0767.94028
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.