×

Dissemination of information in interconnection networks (broadcasting & gossiping). (English) Zbl 0840.68088

Du, Ding-Zhu (ed.) et al., Combinatorial network theory. Dordrecht: Kluwer Academic Publishers. Appl. Optim. 1, 125-212 (1996).
Summary: The main aims of this work are the following:
1) To provide an easily readable introduction (suitable also for undergraduate students) to the research area dealing with the dissemination of information in distinct interconnection networks.
2) To explain some of the basic proof techniques and ideas leading to some important results of this area.
3) To give a survey of established results, especially for broadcasting and gossiping in the extensively studied telegraph and telephone communication mode, and to formulate some open problems interesting for this research area.
The structure of this article follows the aims stated above. The first section introduces this research area. The basic definitions are given and the fundamental, simple observations concerning the relations among the complexity measures defined are carefully explained. This section is devoted to people who have never worked in this area and can be skipped by anybody who is familiar with this topic. The notation fixed here is the usual one used in the literature.
The second section is devoted to broadcasting, and it presents some of the main techniques and results connected to broadcast problems in the one-way (telegraph) communication mode.
The third section is devoted to gossiping in the one-way (telegraph) communication mode and in the two-way (telephone) communication mode. It provides also some basic ideas, a survey of the known results, and the formulation of open problems.
The last section provides a short survey of broadcasting and gossiping in other communication modes. It also discusses other possibilities than the number of communication rounds to measure the complexity of information dissemination.
Finally, we give a list of all publications devoted to this topic which are currently known to us.
For the entire collection see [Zbl 0834.00018].

MSC:

68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
90B18 Communication networks in operations research
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
PDFBibTeX XMLCite