𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Further gossip problems

✍ Scribed by D.J. Kleitman; J.B. Shearer

Book ID
103056378
Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
617 KB
Volume
30
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

n people have distinct bits of information. They can communicate via k-party conference calls. I-Iow many such calls are needed to inform everyone of everyone else's information? Let f(n, k) be this minimum number.

Then we give a simple proof that

for n>k2. In the 2-party case we consider the case in which certain of the calls may permit information flow in only one direction. We show that any 2n-4 call scheme that conveys everone's information to all must contain a 4-cycle, each of whose calls is "two way", along with some other results. The method follows that of Bumby who first proved the 4-cycle conjecture, This paper contains several results on "gossip problems" that follow from Bumby's approach i'o it. These are discussed in the following two sections.

πŸ“œ SIMILAR VOLUMES

The gossip problem
The gossip problem
✍ Gerald Berman πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 75 KB
The exact gossiping problem
The exact gossiping problem
✍ Yuh-Jiuan Tsay; Gerard J Chang πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 297 KB

This paper studies a variation of the gossiping problem, where there are n persons, each of whom initially has a message. A pair of persons can pass all messages they have by making one telephone call. The exact gossiping problem is to determine the minimum n,,mi~er of calls for each person to know

The partial gossiping problem
The partial gossiping problem
✍ Gerard J. Chang; Yuh-Jiuan Tsay πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 275 KB

This paper studies the following variation of the gossiping problem. Suppose there are n persons, each of whom knows a message. A pair of persons can pass all messages they have by making a telephone call. The partial gossiping problem is to determine the minimum number of calls needed for each pers

Gossip, Gossipers, Gossiping
Gossip, Gossipers, Gossiping
✍ Fine, G. A.; Rosnow, R. L. πŸ“‚ Article πŸ“… 1978 πŸ› SAGE Publications 🌐 English βš– 920 KB
Label-connected graphs and the gossip pr
Label-connected graphs and the gossip problem
✍ 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)