𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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


Some minimum gossip graphs
✍ Roger Labahn πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 715 KB
A study of minimum gossip graphs
✍ Guillaume Fertin πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 294 KB
Label-connected graphs and the gossip pr
✍ F. GΓΆbel; J.Orestes Cerdeira; H.J. Veldman πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 791 KB

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)

Cyclic gossiping times for some classes
✍ Knisely, James A.; Laskar, Renu πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 574 KB

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