zbMATH — the first resource for mathematics

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.

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[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, (), 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, 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, (), 351-362
[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, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.