{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:47Z","timestamp":1787337467149,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Gossiping is the process of information diffusion in which each node of a network holds a packet that must be communicated to all other nodes in the network. We consider the problem of gossiping in communication networks under the restriction that communicating nodes can exchange up to a fixed number p of packets at each round. In the first part of the paper we study the extremal case p=1 and we exactly determine the optimal number of communication rounds to perform gossiping for several classes of graphs, including Hamiltonian graphs and complete k-ary trees. For arbitrary graphs we give asymptotically matching upper and lower bounds. We also study the case of arbitrary p and we exactly determine the optimal number of communication rounds to perform gossiping under this hypothesis for complete graphs, hypercubes, rings, and paths. Finally, we investigate the problem of determining sparse networks in which gossiping can be performed in the minimum possible number of rounds.<\/jats:p>","DOI":"10.1137\/s0097539795283619","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"917-941","source":"Crossref","is-referenced-by-count":26,"title":["Fast Gossiping by Short Messages"],"prefix":"10.1137","volume":"27","author":[{"given":"Jean-Claude","family":"Bermond","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luisa","family":"Gargano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adele A.","family":"Rescigno","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ugo","family":"Vaccaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192236628"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90042-4"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220402"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790192672"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230260302"},{"key":"R6","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1989."},{"key":"R7","doi-asserted-by":"publisher","unstructured":"Bogdan Chlebus, Krzysztof Diks, Andrzej Pelc, Fast gossiping with short unreliable messages, Proceedings International Workshop on Broadcasting and Gossiping 1990 (Sechelt, BC), Vol. 53, 1994, 15\u20132410.1016\/0166-218X(94)90176-795g:90026","DOI":"10.1016\/0166-218X(94)90176-7"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0409002"},{"key":"R9","unstructured":"G. Fox, M. Johnsson, G. Lyzenga, S. Otto, J. Salmon, and D. Walker,\n                      Solving Problems on Concurrent Processors, Volume I\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1988."},{"key":"R10","doi-asserted-by":"publisher","unstructured":"Pierre Fraigniaud, Emmanuel Lazard, Methods and problems of communication in usual networks, Proceedings International Workshop on Broadcasting and Gossiping 1990 (Sechelt, BC), Vol. 53, 1994, 79\u201313310.1016\/0166-218X(94)90180-595f:68015","DOI":"10.1016\/0166-218X(94)90180-5"},{"key":"R11","first-page":"41","volume":"36","author":"Fujita S.","year":"1993","journal-title":"IPS Japan SIGAL"},{"key":"R12","unstructured":"Martin F\u00fcrer, Balaji Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, ACM, New York, 1992, 317\u20133241173903"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0404021"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193245923"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180406"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Hily and D. Sotteau,\n                      Communications in Bus Networks\n                      , in Parallel and Distributed Computing, Lectures Notes in Computer Science 805, M. Cosnard, A. Ferreira, and J. Peters, eds., Springer\u2010Verlag, New York, 1994, pp. 197\u2013206.","DOI":"10.1007\/3-540-58078-6_17"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Juraj Hromkovi\u010d, Ralf Klasing, Burkhard Monien, Regine Peine, Dissemination of information in interconnection networks (broadcasting & gossiping), Appl. Optim., Vol. 1, Kluwer Acad. Publ., Dordrecht, 1996, 125\u201321298d:68027","DOI":"10.1007\/978-1-4757-2491-2_5"},{"key":"R18","unstructured":"S. L. Johnsson and C. T. Ho,\n                      Matrix multiplication on Boolean cubes using generic communication primitives\n                      , in Parallel Processing and Medium\u2010Scale Multiprocessors, A. Wouk, ed., SIAM, Philadelphia, 1989, pp. 108\u2013156."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0221026"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0221010"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230416"},{"key":"R22","unstructured":"R. Ravi, private communication."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"R. Ravi,\n                      Rapid rumor ramification: Approximating the minimum broadcasting time\n                      , in Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS \u201994), 1994, pp. 202\u2013213.","DOI":"10.1109\/SFCS.1994.365693"},{"key":"R24","unstructured":"J. de Rumeur,\n                      Communication dans les Reseaux de Processeur\n                      , Masson, Paris, 1994."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795283619","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:11:56Z","timestamp":1787335916000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795283619"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795283619"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795283619","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}