Broadcasting in DMA-bound bounded degree graphs. (English) Zbl 0755.94018
Summary: 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. Bermond, Hell, Liestman and Peters studied the effect, on broadcasting capabilities, of placing an upper bound on the graph’s degree. In this paper, we generalize their results by allowing calls to involve more than two participants. We give lower bounds and construct bounded degree graphs which allow rapid broadcasting. Our construction use the notion of compounding graphs in de Bruijn digraphs. We also obtain asymptotic upper and lower bounds for broadcast time, as the maximum degree increases.
MSC:
| 94C15 | Applications of graph theory to circuits and networks |
| 94A05 | Communication theory |
| 05C20 | Directed graphs (digraphs), tournaments |
Keywords:
communication networks; Broadcasting; information dissemination; graphs; compounding graphs; de Bruijn digraphs; broadcast timeReferences:
| [1] | Bermond, J. C.; Delorme, C.; Quisquater, J. J., Strategies for interconnection networks: Some methods from graph theory, J. Parallel Distribut. Comput., 3, 433-449 (1986) |
| [2] | Bermond, J. C.; Hell, P.; Liestman, A. L.; Peters, J. G., Broadcasting in bounded degree graphs, (Tech. Rep. 88-5 (1988), Simon Fraser University: Simon Fraser University Burnaby, B.C) · Zbl 0753.68007 |
| [3] | 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 |
| [4] | Bermond, J. C.; Peyrat, C., Broadcasting in de Bruijin networks, Proceedings of the 19th Southeastern Conference on Graph Theory and Computing. Proceedings of the 19th Southeastern Conference on Graph Theory and Computing, Congr. Numer., 66, 283-292 (1988), Baton Rouge · Zbl 0673.94027 |
| [5] | Bondy, J. A.; Murty, U. S.R., Graph Theory With Applications (1976), Macmillan: Macmillan New York · Zbl 1134.05001 |
| [6] | Capocelli, R. M.; Gargano, L.; Vaccaro, U., Time bounds for broadcasting in bounded degree graphs, WG 89 15th International Workshop on Graphtheoretic Concepts in Computer Science, 19-33 (1989), Rolduc · Zbl 0768.68123 |
| [7] | Chau, S. C.; Liestman, A. L., Constructing minimal broadcast networks, J. Combin. Inform. System Sci., 10, 110-122 (1985) · Zbl 0696.90077 |
| [8] | de Bruijin, N. G., A combinatorial problem, Nederl. Akad. Wetensch. Proc. Ser. A, 49, 758-764 (1946) · Zbl 0060.02701 |
| [9] | Farley, A., Minimal broadcast networks, Networks, 9, 313-332 (1979) · Zbl 0425.94025 |
| [10] | Farley, A.; Hedetniemi, S.; Mitchell, S.; Proskurowski, A., Minimum broadcast graphs, Discrete Math., 25, 189-193 (1979) · Zbl 0404.05038 |
| [11] | Fraigniaud, P., Complexity analysis of brodcasting in hypercubes with restricted communication capabilities, (Tech. Rept. (1989), LIP-IMAG, University of Lyon) · Zbl 0763.68039 |
| [12] | Grigni, M.; Peleg, D., Tight bounds on minimum broadcast networks, SIAM J. Discrete Math., 4, 207-222 (1991) · Zbl 0725.94016 |
| [13] | Hedetneimi, S. M.; Hedetniemi, S. T.; Liestman, A. L., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047 |
| [14] | Heydemann, M. C.; Opatrny, J.; Sotteau, D., Broadcasting and spanning trees in de Bruijin and Kautz networks, (LRI Tech. Rept. 526 (1989), University of Paris-Sud: University of Paris-Sud Orsay Cedex) · Zbl 0755.94017 |
| [15] | Hillis, W. D., The Connection Machine, (ACM Distinguished Dissertations (1985), MIT Press: MIT Press Cambridge, MA) |
| [16] | Ho, C. T.; Johnson, S. L., Distributed routing algorithms for broadcasting and personalized communications in hypercubes, Proceedings 1986 International Conference on Parallel Processing, 640-648 (1986) |
| [17] | Johnson, D.; Garey, M., Graph Theory With Applications (1979), Freeman: Freeman San Francisco, CA |
| [18] | Johnson, S. L.; Ho, C. T., Optimum broadcasting and personalized communication in hypercubes, IEEE Trans. Comput., 38, 1249-1268 (1989) · Zbl 1395.68034 |
| [19] | Lazard, E., Broadcasting in DMA-bound bounded degree graphs, (LRI Tech. Rept. 536 (1990), University of Paris-Sud: University of Paris-Sud Orsay Cedex) · Zbl 0755.94018 |
| [20] | Liestman, A. L.; Peters, J. G., Broadcast networks of bounded degree, SIAM J. Discrete Math., 1, 531-540 (1988) · Zbl 0662.94027 |
| [21] | Liestman, A. L.; Peters, J. G., Minimum broadcast digraphs, (Tech. Rept. 89-3 (1989), Simon Fraser University: Simon Fraser University Burnaby, B.C) · Zbl 0755.94019 |
| [22] | Miles, E. P., Generalized Fibonacci numbers and matrices, Amer. Math. Monthly, 67, 745-757 (1960) · Zbl 0103.27203 |
| [23] | Mitchell, S.; Hedetniemi, S., A census of minimum broadcast graphs, J. Combin. Inform. System Sci., 5, 141-151 (1980) · Zbl 0449.05034 |
| [24] | Saad, Y.; Schultz, M. H., Data communication in hypercubes, J. Parallel Distribut. Comput., 6, 115-135 (1989) |
| [25] | Stout, Q. F.; Wager, B., Intensive hypercube communication I: Prearranged communication in link-bound machines, J. Parallel Distribut. Comput., 10, 167-181 (1990) |
| [26] | Wang, X., Manuscript (1986) |
| [27] | P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks, Discrete Appl. Math., to appear.; P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks, Discrete Appl. Math., to appear. · Zbl 0818.94029 |
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.
