On gossiping with faulty telephone lines
On gossiping with faulty telephone lines
复制标题
关于用有故障的电话线闲聊
DOI：
10.1137/0608036
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
A. Schäffer
中科院分区：
文献类型：
--
作者：
R. Haddad;S. Roy;A. Schäffer
在著名的流言问题中，n个流言中的每一个最初都有一条唯一的信息。八卦者可以进行一系列的两方电话通话，其中两个参与者在通话时交换他们所拥有的每一条信息。问题是确定一个最小长度的电话序列，这样，到最后，每个人都知道其他人的信息。我们认为伯曼和Hawrylycz的变化对这个问题[本杂志，7（1986），页。13-17]。它们引入了一个额外的特征，即在没有信息交换的意义上，多达k个调用可能会失败，其中k是问题的第二个参数。我们改进了他们的上限上所需的最小调用次数。这反驳了同一篇论文中的一个猜想。我们还简要地考虑了这个问题的并行复杂性。
In the well-known gossip problem, each of n gossips initially has a unique piece of information. The gossips can make a sequence of two-party telephone calls in which the two participants exchange every piece of information they have at the time of the call. The problem is to determine a minimum length sequence of telephone calls such that, by the end, everyone knows everyone else’s information. We consider Berman and Hawrylycz’s variation on this problem [this Journal, 7 (1986), pp. 13–17]. They introduce the additional feature that as many as k of the calls may fail in the sense that no information is exchanged, where k is a second parameter of the problem. We improve upon their upper bound on the minimum number of calls needed. This disproves a conjecture in the same paper. We also briefly consider the parallel complexity of this problem.