Compounding of gossip graphs
β Scribed by Guillaume Fertin; Roger Labahn
- Book ID
- 101320982
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 262 KB
- Volume
- 36
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
β¦ Synopsis
Gossiping refers to the following task: In a group of individuals connected by a communication network, every node has a piece of information and needs to transmit it to all the nodes in the network. The networks are modeled by graphs, where the vertices represent the nodes, and the edges, the communication links. In this paper, we concentrate on minimum gossip graphs of even order, that is, graphs able to achieve gossiping in minimum time and with a minimum number of links. More precisely, we derive upper bounds for their number of edges from a compounding method, the k-way split method, previously introduced for broadcasting by Farley [Networks 9 (1979), 313-332]. We show that this method can be applied to gossiping in some cases and that this generalizes some compounding methods for gossip graphs given in . We also show that, when applicable, this method gives the bestknown upper bounds on the size of minimum gossip graphs in most cases, either improving or matching them. Notably, we present for the first time two families of regular gossip graphs of order n n n and of degree log 2 (n n n) ---3 and log 2 (n n n) ---4, respectively. We also give some lower bounds on the number of edges of gossip graphs which improve the ones given by Fertin . Moreover, we show that the above compounding method also applies for minimum linear gossip graphs (or MLGGs) of even order, which corresponds to a variant of gossiping where the time of information transmission between two nodes depends on the amount of information exchanged. We also prove that this gives the bestknown upper bounds for G G G Ξ² Ξ² Ξ²,Ο Ο Ο (n n n)-the size of an MLGG of order n n n-in most cases. In particular, we derive from this method the exact value of G G G Ξ² Ξ² Ξ²,Ο Ο Ο (72), which was previously unknown.
π SIMILAR VOLUMES
Gobel, F., J. Orestes Cerdeira and H.J. Veldman, Label-connected graphs and the gossip problem, Discrete Mathematics 87 (1991) 29-40. A graph with m edges is called label-connected if the edges can be labeled with real numbers in such a way that, for every pair (u, v) of vertices, there is a (u, v)
Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping, every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting, one individu