×

Note on optimal gossiping in some weak-connected graphs. (English) Zbl 0824.68010

Summary: The problems of gossiping and broadcasting in one-way communication mode are investigated. Optimal algorithms for gossip problem are known only for the complete graphs, paths, some simple trees, and cycles. In this paper some lower bounds on gossiping in graphs with bridges or with edge disjoint cycles are proved. A direct consequence of these lower bounds is the construction of optimal gossip algorithms for some families of weak- connected graphs.
Another question considered here is the relationship between the gossip problem and the broadcast problem. Gossiping cannot be more than twice as hard as broadcasting, and only for trees it is known that gossiping is exactly two times harder than broadcasting. Using the above-mentioned lower bounds some other graphs (having cycles) with this property are found.

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bagchi, A.; Hakimi, S. L.; Mitchem, J.; Schmeichel, E., Parallel algorithms for gossiping by mail, Inform. Process. Lett., 34, 197-202 (1990) · Zbl 0696.68048
[2] Baker, B.; Shostak, R., Gossips and telephones, Discr. Math., 2, 191-193 (1972) · Zbl 0245.05002
[3] Bermond, J.-C.; Peyrat, C., Broadcasting in DeBruijn networks, (Proc. 19th Southeastern Conference on Combinatorics, Graph Theory and Computing. Proc. 19th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium 66 (1988)), 283-292 · Zbl 0673.94027
[4] Cybenko, G.; Krumme, D. W.; Venkataraman, K. N., Gossiping in minimal time, SIAM J. Comput., 21, 111-139 (1992) · Zbl 0743.68039
[5] Entringer, R. C.; Slater, P. J., Gossips and telegraphs, J. Franklin Institute, 307, 353-360 (1979) · Zbl 0408.05051
[6] Even, S.; Monien, B., On the number of rounds necessary to disseminate information, Santa Fe. Santa Fe, Proc. 1st ACM Symp. on Parallel Algorithms and Architectures, 318-327 (1989)
[7] Farley, A. M.; Proskurowski, A., Gossiping in grid graphs, J. Combin. Inform. System Sci., 5, 161-172 (1980) · Zbl 0443.68049
[8] Hajnal, A.; Milner, E. C.; Szemeredi, E., A cure for the telephone disease, Can. Math. Bull., 15, 447-450 (1972) · Zbl 0251.05132
[9] Hedetniemi, 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
[10] Hromkovič, J.; Jeschke, C. D.; Monien, B., Optimal algorithms for dissemination of information in some interconnection networks, Algorithmica, 10, 24-40 (1993) · Zbl 0773.68007
[11] Klasing, R.; Monien, B.; Peine, R.; Stöhr, E., Broadcasting in Butterfly and De Bruin networks, (Proc. STACS’92. Proc. STACS’92, Lecture Notes in Computer Science, Vol. 577 (1992), Springer: Springer Berlin), 351-362 · Zbl 1494.68020
[12] Knödel, W., New gossips and telephones, Discr. Math., 13, 95 (1975) · Zbl 0305.05001
[13] Krumme, D. W., Fast gossiping for the hypercube, SIAM J. Comput., 21, 365-380 (1992) · Zbl 0747.68010
[14] Labahn, R.; Warnke, I., Quick gossiping by multi-telegraphs, (Bodendiel, R.; Henn, K., Topics in Combinatorics and Graph Theory (1990), Physica: Physica Heidelberg), 451-458 · Zbl 0749.05061
[15] Liestman, A. L.; Peters, J. G., Broadcast networks of bounded degree, SIAM J. Discr. Math., 1, 531-540 (1988) · Zbl 0662.94027
[16] Richards, D.; Liestman, A. L., Generalization of broadcasting and gossiping, Network, 18, 125-138 (1988) · Zbl 0709.90540
[17] Stöhr, E., Broadcasting in the butterfly network, Inform. Process. Lett., 39, 41-43 (1991) · Zbl 0735.68008
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.