The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.5 / (1996))
Optimal Group Gossiping in Hypercubes Under a Cirsuit-Switching Model
Satoshi Fujita, Masafumi Yamashita,
Pages. 1045-1060
Abstract
Contents 1. Introduction
2. Preliminaries
2.1. Notation
2.2. Circuit-switching model
2.3. Group-gossiping problem
3. Outline of algorithm GROUP_GOSSIP 1
4. Communication with intermediate nodes
4.1. Intermediate nodes $W$
4.2. Edge-disjoint paths connecting $U$ and $W$
5. Exchange tokens among intermediate nodes
5.1. Basic communication routes
5.2. Exchange tokens among all nodes in $W$
6. The second algorithm, GROUP_GOSSIP 2
7. Concluding remarks
Key words parallel algorithm, gossiping, circuit-switching model, optimal-time bound, $n$-cubes.
Mathmatical Subject Classification 05C38, 68Q20, 68R10