Families of Graphs Having Broadcasting and Gossiping Properties
| 详细信息 | 推荐本文 | |
- 作者：Guillaume Fertin ; Andr茅 Raspaud
- 关键词：Broadcasting ; gossiping ; minimum broadcast graphs ; minimum gossip graphs ; Kn枚del graphs ; circulant graphs ; hypercubes
- 刊名：Lecture Notes in Computer Science
- 出版时间：1998
- 出版年：1998
- 期刊代码：99_0302-9743
- 类别：cp
- 卷：1517
- 期：1
- 页码：753-767
- 数据来源：sp
摘要
Broadcasting and gossiping are two problems of information dissemination described in a group of individuals connected by a communication network. In broadcasting (resp. gossiping), one node (resp. every node) has a piece of information and needs to transmit it to everyone else in the network. These communications patterns find their main applications in the field of interconnection networks for parallel architectures. In this paper, we are interested in Minimum Broadcast (resp. Gossip, Linear Gossip) Graphs (resp. Digraphs), that is graphs (resp. digraphs) that can achieve broadcasting (resp. gossiping, linear gossiping) in minimum time, and with a minimum number of edges. Many papers have investigated these subjects, but only a few general results on the size of graphs of order n are known. In this paper, we take the census of all the known non-isomorphic families of graphs (resp. digraphs) which are Minimum Broadcast Graphs, Minimum Gossip Graphs, Minimum Linear Gossip Graphs and/or Minimum Broadcast Digraphs, and we show that in most cases, the proposed minimum graphs that can be found in the literature are Kn枚del graphs [10,7].