The Gossip Problem:
There are n ladies, and each of them knows some item of gossip
not known to the others. They communicate by telephone, and
whenever one lady calls another, they tell each other all that
they know at that time. How many calls are required before each
gossip knows everything?
Solution:
[Baker; Shostak], [Bumby], [Hajnal; Milner; Szemerédi] and [Tijdeman]
showed with different methods that 2n - 4 calls are needed for n>=4.
The proof of optimality is difficult and takes at least a page.
With two additional calls a further gossip can participate.
But n = 4 is critical, where one call can be saved.
n=4: A---1---D The four ladies are A, B, C, and D.
| |
3 4 The edges 1 to 4 give the calls in this order.
| |
B---2---C
[Lebensold] generalized the problem for telephone conferences
of k persons. This proof was simplified by [Kleitman, Shearer].
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
References:
- Brenda Baker, Robert Shostak;
Gossips and Telephones,
Discrete Mathematics 2 (1972) 191-193
MR 46 # 68
- Gerald Berman;
The Gossip problem,
Discrete Mathematics 4 (1973) 91 (Corrigendum p397)
MR 46 # 7037
- J.-C. Bermond;
Le problème des "ouvroirs". (French. English summary)
Problèmes combinatoires et théorie des graphes
(Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 31--34,
Colloq. Internat. CNRS, 260, CNRS, Paris, 1978.
MR 81c:05056
- Richard T. Bumby;
A problem with telephones,
SIAM J. Alg. Disc. Meth. 2 (1981) 13-18
MR 82f:05083
(mailto:bumby@math.rutgers.edu)
- Hajnal, A.; Milner, E. C.; Szemerédi, E. ;
A cure for the telephone disease.
Canad. Math. Bull. 15 (1972), 447--450.
MR 47 #3184
- F. Harary; B. Raghavachari;
The E-mail Gossip Number and the connected Domination Number,
Appl. Math. Letter 10:4 (1997) 15-17
- e-mail can be sent to all neighbors of a vertex in one step.
Let eg(G) be the minimal number of e-mails to be sent.
1) eg(K_n) = n, as any sending sequence of all n nodes will do.
2) eg(C_n) = 2n-3, using the sending node sequence 1,2...n,1,2...n-3
- D. J. Kleitman, J. B. Shearer;
Further Gossip Problems,
Discrete Mathematics 30 (1980) 151-156
MR 81d:05068
- R. Labahn;
Kermels of minimum size gossip schemes,
Discrete Mathematics 143 (1995) 99-139
- Kenneth Lebensold;
Efficient communication by phone calls,
Studies in Appl. Math. 52 (1973) 345-358
MR 49 #4797
- Tijdeman, R. ;
On a telephone problem.
Nieuw Arch. Wisk. (3) 19 (1971), 188-192.
MR 49 #7151
- Ioan Tomescu;
Introduction to Combinatorics,
- The gossip problem (Baker, Shostak and Hajnal, Milner, Szemerdi, 1972)
There are n gossips each of whom knows some gossip not known to the
others. They communicate by telephone, and whenever one gossip calls
another, they tell each other all they know at that time.
Prove that the minimum number of calls required before each gossip knows
everything is equal to 2n-4 for n>=4.
- S. S. Wadhwa;
PARAB 372 (gossip problem for n=5),
Parabola, Proposal: 14(1978/1)28 Solution: 14(1978/3)31 by S. S. Wadhwa
After the first day of classes, each of 5 different students knows a
different bit of gossip about the teachers in their school. When they
get to their separate homes, the telephoning begins. Assume that whenever
anyone calls anyone else, each tells the other all the gossip he knows.
What is the smallest number of calls after which it is possible for
every student to know all 5 bits of gossip?
Reviews:
- Brenda Baker, Robert Shostak;
Gossips and Telephones,
Discrete Mathematics 2 (1972) 191-193
MR 46 # 68
From the authors' introduction: "The problem: There are $n$ ladies, and each
of them knows some item of gossip not known to the others. They communicate
by telephone, and whenever one lady calls another, they tell each other all
that they know at that time. How many calls are required before each gossip
knows everything? Answer: Let $f(n)$ be the minimum number of calls needed
for $n$ people. It is easily shown that $f(1)=0$, $f(2)=1$, $f(3)=3$ and
$f(4)=4cient according to the following
procedure: one of four `chief' gossips first calls each of the remaining
$n-4$ gossips, then the four learn each other's (and hence everyone's)
information in 4 calls (as $f(4)=4$), and finally one of the four chiefs
calls each of the other $n-4$ gossips. Theorem 1: $f(n)=2n-4$ for $n>4$."
- Gerald Berman;
The Gossip problem,
Discrete Mathematics 4 (1973) 91 (Corrigendum p397)
MR 46 # 7037
The author gives a simple (but, as pointed out in the corrigendum, incomplete)
solution of the gossip problem of B. Baker and R. Shostack [Discrete Math. 2
(1972), no. 3, 191--193; MR 46 #68].
- Hajnal, A.; Milner, E. C.; Szemerédi, E. ;
A cure for the telephone disease.
Canad. Math. Bull. 15 (1972), 447--450.
MR 47 #3184
Consider the following situation: There are $n$ people, each knowing an
item of information not known to any of the others. They communicate by
telephone and whenever two people talk to one another during a call, each
informs the other of all the information known at the time. The problem
is to determine the minimum number $f(n)$ of calls needed for everyone to
know all the information.
In this note the authors elegantly prove the surprisingly stubborn result
that $f(n)=2n-4$ for $n\geq 4$. A proof along somewhat different lines has
been given by B. Baker and R. Shostak [Discrete Math. 2 (1972), no. 3,
191--193; MR 46 #68].
Reviewed by R. L. Graham
- J.-C. Bermond;
Le problème des "ouvroirs". (French. English summary)
Problèmes combinatoires et théorie des graphes
(Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 31--34,
Colloq. Internat. CNRS, 260, CNRS, Paris, 1978.
MR 81c:05056
This paper contains one of two recent short proofs of the "conference call"
generalization of the gossip problem formulated and originally solved by K.
Lebensold [Stud. Appl. Math. 52 (1973), 345--358; MR 49 #4797]. The method
is based on that of A. Hajnal, E. C. Milner and E. Szemeredi [Canad. Math. Bull.
15 (1972), 447--450; MR 47 #3184] and thus gives detailed information about
the set of elements which "know everything" after $m$ calls.
An independent proof using different methods has also been given by D. J.
Kleitman and J. B. Shearer [Discrete Math. 30 (1980), no. 2, 151--156;
MR 81d:05068].
Reviewed by Richard T. Bumby
- Richard T. Bumby;
A problem with telephones,
SIAM J. Alg. Disc. Meth. 2 (1981) 13-18
MR 82f:05083
The "telephone problem", also known as the "gossip problem", asks for the
minimum number of calls required for $n$ people, for each to learn the others'
information (gossip). The answer is $2n-4$. The author proves the "four-cycle
conjecture": A graph whose edges are the calls of such a minimum set contains a
four-cycle. Other properties of a minimum set of calls are obtained. D. J.
Kleitman and J. B. Shearer [Discrete Math. 30 (1980), no. 2, 151--156;
MR 81d:05068] Most of the four-cycle conjecture, based on the author's proof,
and other related results.
Reviewed by J. R. Griggs
- D. J. Kleitman, J. B. Shearer;
Further Gossip Problems,
Discrete Mathematics 30 (1980) 151-156
MR 81d:05068
Starting from work of the reviewer ["A problem with telephones", SIAM J.
Algebraic Discrete Methods, to appear] on the "gossip problem" and "4-cycle
conjecture", the authors give additional properties which may be required of a
4-cycle in the graph of $2n-4$ calls pooling the information of $n$ people. A
brief proof of the strengthened theorem is then given.
In addition, similar methods are used to simplify a result of K. Lebensold
[Studies in Appl. Math. 52 (1973), 345--358; MR 49 #4797] on conference calls.
The result is also simplified by giving a more natural formula for the minimum
number of calls. The proof is quite different from that recently published by
J.-C. Bermond [Problemes combinatoires et theorie des graphes (Colloq.
Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 31--34, CNRS, Paris, 1978].
Reviewed by Richard T. Bumby
- Kenneth Lebensold;
Efficient communication by phone calls,
Studies in Appl. Math. 52 (1973) 345-358
MR 49 #4797
Let $f(n,k)$ denote the number of phone calls needed for $n$ persons to pool all
their information in a succession of $k$-person party line phone calls. The
author proves that $f(n,k)=[(n-2)/(k-1)]+[(n-1)/k]+1$ if $1\leq n\leq k\sp 2$
and $f(n,k)=2[(n-2)/(k-1)]$ for $n>k\sp 2$.
Reviewed by M. S. Cheema
- Tijdeman, R. ;
On a telephone problem.
Nieuw Arch. Wisk. (3) 19 (1971), 188--192.
MR 49 #7151
A set of $n$ people, each initially possessing a unique item of information,
make a sequence of telephone calls. During a call, the two parties tell one
another the total amount of information known at the time. How many calls
are necessary for everyone to know everything? This is the problem solved by
the author, the answer being $2n-4$ when $n\geq 4$ and $0,1,3$ for $n=1,2,3$,
respectively.
The question is attributed to A. Boyd although, to the best of the reviewer's
knowledge, it was first formulated by R. Chesters and S. Silverman (Univ. of
Witwatersrand, unpublished, 1970). Previous solutions have been given by A.
Hajnal, E. C. Milner and E. Szemeredi [Canad. Math. Bull. 15 (1972), 447--450;
MR 47 #3184], B. Baker and R. Shostak [Dissertationes Math. 2 (1972), no. 3,
191--193; MR 46 #68], R. Bumby (unpublished) and J. H. Spencer (unpublished).
Reviewed by R. L. Graham
- Kn\"odel, Walter
New gossips and telephones.
Discrete Math. 13 (1975), no. 1, 95.
MR 51 #15169
Consider $n$ persons, each of whom wants to telephone his one bit of
information to all the others by means of a sequence of binary messages each of
which has a fixed transmission time. The problem is to find how much time is
required before ea .....
B. Baker and R. Shostak [Discrete Math. 2 (1972), no. 3, 191--193; MR 46 #68]
showed that $2n-4$ calls are sufficient for $n>4$.
In this short note the author establishes by a simple
combinatorial argument that the optimal lower bounds are
$\lceil\log\sb 2n\rceil$ for even $n$ and $\lceil\log\sb 2n\rceil+1$
for odd $n$.
Reviewed by H. P. Edmundson
- Cot, Norbert
Extensions of the telephone problem.
Proceedings of the Seventh Southeastern Conference
on Combinatorics, Graph Theory, and Computing
(Louisiana State Univ., Baton Rouge, La., 1976), pp. 239--256.
Congressus Numerantium, No. XVII,
Utilitas Math., Winnipeg, Man., 1976.
MR 55 #2375
The telephone problem, known as the "gossip problem", first suggested by Erdos
is considered. Solutions to the original problem were given by B. Baker and R.
Shoshtak [Discrete Math. 2 (1972), 191--193; MR 46 #68] and some properties
of the optimal solutions are discussed in this paper. Four possible extensions
of the classical problem are then proposed; they are related to the following
considerations:
(a) the connections between the elements (i.e., gossips),
(b) the ways these elements communicate,
(c) the information they exchange, and
(d) the quantities or functions to be minimized.
The connections between the elements in the initial problem form a complete
and undirected graph. In general, the graph which represents the connections
is directed and not complete or undirected and not complete.
A conjecture of Golumbic dealing with undirected graphs without 4-cycles is
considered and the author proves it for a subclass of such graphs.
Reviewed by M. M. Syslo
- Krumme, David W.(1-TUFT-C)
Reordered gossip schemes. (English. English summary)
Discrete Math. 156 (1996), no. 1-3, 113--140.
97i:68154
Gossiping is a communication task in which each node of a graph has a piece of
information which has to reach all other nodes. Communication is done by
performing telephone calls along the edges of the graph. Every node can
participate in at most one call at a time and during a call participating nodes
exchange all previously accumulated information.
The author proves a structural theorem concerning schemes of calls that achieve
gossiping. The theorem says that calls of every such scheme can be rearranged
into a sequence such that at most two calls cause each node to become fully
informed and that the reverse sequence has the same property. This rather
technical result has many important consequences. The author obtains
well-known and important results from the theory of gossiping as easy
corollaries of his theorem. For example he obtains a theorem stating that the
smallest number of calls for gossiping in a complete $n$-node graph is $2n-4$
[cf. R. T. Bumby, SIAM J. Algebraic Discrete Methods 2 (1981), no. 1, 13--18;
MR 82f:05083]. As such, the structural theorem adds a unifyi important
application of the theorem is the solution of an open problem stated by
N. Cot and unsolved for 20 years [cf. in Proceedings of the Seventh
Southeastern Conference on Combinatorics, Graph Theory, and Computing
(Louisiana State Univ., Baton Rouge, La., 1976), 239--256, Congressus
Numerantium, XVII, Utilitas Math., Winnipeg, Man., 1976; MR 55 #2375].
It concerns the following generalization of the problem of finding a
gossiping scheme with a minimum number of calls. Suppose that every edge of a
graph is given a positive number representing the cost of calling along this
edge. What is the minimum cost of a gossiping scheme (i.e., the minimum sum of
costs of all calls)? It has been conjectured by O. Wolfson and A. Segall
[SIAM J. Comput. 20 (1991), no. 3, 423--450; MR 91k:68037] that finding this
minimum cost is NP-hard. Using his theorem the author gives a polynomial
algorithm to find a minimum cost gossiping. More precisely, his algorithm
works in time $O(n\sp 2m)$, where $n$ is the number of nodes and $m$ is the
number of edges.
Reviewed by Andrzej Pelc
- G\"obel, F.(NL-TWEN-A); Cerdeira, J. Orestes; Veldman, H. J.(NL-TWEN-A)
Label-connected graphs and the gossip problem.
Discrete Math. 87 (1991), no. 1, 29--40.
MR 92a:05074
The gossip problem is to determine the minimum number of telephone calls
which must be made among $n$ persons so that each person can obtain the
information known by all the other persons, assuming that when a call is made,
the two persons share all the information available to them. This minimum
number is known to be $2n-4$ [see, e.g., R. T. Bumby, SIAM J. Algebraic
Discrete Methods 2 (1981), no. 1, 13--18; MR 82f:05083]. In the present paper
the authors define a graph $G$ to be label-connected if it is possible to assign
to each edge of $G$ a real number in such a way that for any two vertices
$u$, $v$ of $G$, there exists a path from $u$ to $v$ along which the edge labels
are in ascending order. Thus if the edge labels correspond to the time of the
telephone calls, finding the minimum number of edges in a label-connected graph
on $n$ vertices is equivalent to solving the gossip problem.
The authors observe that if $\varphi(G)\leq 1$, then $G$ is label-connected, and
that if $G$ is label-connected, then $\varphi(G)\leq 2$, where $\varphi(G)$ is
the number of edges which must be added to $G$ to form two disjoint spanning
trees. While each of these conditions can be checked in polynomial time, the
authors show that when $\varphi(G)=2$, determining whether or not $G$ is
label-connected is NP-complete. In the special case when $G$ has $n$ vertices
and $2n-4$ edges, the authors show that $G$ is label-connected if and only if
$G$ is a $C\sb 4$-graph, that is, $G=S\sb 1\cup S\sb 2$, where $S\sb 1$ and
$S\sb 2$ are two edge-disjoint spanning forests each having two components,
and $G$ has a four-cycle $uvwxu$ with edges $uv$, $wx$ in distinct
components of $S\sb BæBVFvW2GgrBÂs of $S\sb 2$, thus
affirming the 4-cycle conjecture of F. Harary and A. J. Schwenk [J.
Franklin Inst. 297 (1974), 491--495; MR 50 #1980] about the gossip problem.
Reviewed by Anthony E. Barkauskas
- Jean-Claude Bermond, Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro;
SFB 343 Preprints 94-116, University of Bielefeld
Fast Gossiping by Short Messages
To appear in: SIAM J. Comput.
--
mailto:Torsten.Sillke@uni-bielefeld.de
http://www.mathematik.uni-bielefeld.de/~sillke/