Krumme, David W. Fast gossiping for the hypercube. (English) Zbl 0747.68010 SIAM J. Comput. 21, No. 2, 365-380 (1992). Summary: The gossip problem involves communicating a unique item from every node in a graph to every other node. The minimum time required to do this for the binary hypercube under two models of communication is studied. In the first model, all communication links may be used concurrently but each may only carry information in one direction at a time. In the second, weaker model each node may be involved in only one communication at a time either as sender or receiver. In both cases, simple algorithms exist that are close to optimal. This paper shows that neither of these algorithms is optimal by exhibiting faster algorithms. In the first case, an optimal algorithm is obtained. Cited in 1 ReviewCited in 12 Documents MSC: 68M10 Network design and communication in computer systems 68R10 Graph theory (including graph drawing) in computer science 90B18 Communication networks in operations research 68W10 Parallel algorithms in computer science Keywords:gossiping; hypercube; broadcasting PDFBibTeX XMLCite \textit{D. W. Krumme}, SIAM J. Comput. 21, No. 2, 365--380 (1992; Zbl 0747.68010) Full Text: DOI Link