Method of Local Interchange to Investigate Gossip Problems
Keywords:
Graphs, Networks, Telephone problem, Gossip problemAbstract
In this paper the method of local interchange is introduced to investigate gossip problems. This method is based on a repetitive use of permute higher and permute lower operations, which map one gossip graph with n vertices to another by moving only its edges without changing the labels of edges (the moments of corresponding calls). Using this method we obtain minimum time gossip graphs in which no one hears his own information (NOHO graphs) from gossip graphs based on Knödel graphs. The value of minimal time is T=[log n]. This method also allowed us to find an alternative way of the proof that the number of minimal necessary calls in gossip schemes is 2n-4, n≥4.
References
B. Baker and R. Shostak, “Gossips and telephones", Discrete Math., vol. 2, pp. 191-193, 1972.
R. T. Bumby, A problem with telephones", SIAM J.Alg. Disc. Math., vol. 2, pp. 13-18, 1981.
A. Hajnal, E.C. Milner and E. Szemeredi, “A cure for the telephone disease", Canad. Math Bull., vol. 15, pp. 447-450, 1972.
T. Tijdeman, “On a telephone problem", Nieuw Arch. Wisk., vol. 3, pp. 188-192, 1971.
A. Seress, “Quick gossiping by conference calls", SIAM J. Disc. Math, vol. 1, pp. 109-120, 1988.
D. B. West, “Gossiping without duplicate transmissions", SIAM J. Alg. Disc. Meth., vol. 3, pp. 418-419, 1982.
G. Fertin and A. Respaud, “A survey on Knödel graphs", Discrete Applied Mathematics, vol. 137 (2), pp. 173-195, 2003.
R. Labahn, “Kernels of minimum size gossip schemes", Discr. Math., vol. 143, pp. 99-139, 1995.
R. Labahn, “Some minimum gossip graphs", Networks, vol. 23, pp. 333-341, 1993.
G. Fertin and R. Labahn, “Compounding of gossip graphs", Networks, vol. 36, pp. 126-137, 2000.
A. Bavelas, “Communication pattern in task-oriented groups", J. Acoust. Soc. Amer., vol. 22, pp. 725-730, 1950.
W. Knodel, “New gossips and telephones", Discr. Math., vol. 13, pp. 95, 1975.
Z. Ho and M. Shigeno, “New bounds on the minimum number of calls in failure-tolerant Gossiping", Networks, vol. 53, pp. 35-38, 2009.
K. A. Berman and M. Hawrylycz, “Telephone problems with failures", SIAM J. Alg. Disc. Meth., vol. 7, pp. 13-17, 1987.
R. W. Haddad, S. Roy and A.A. Schaffer, “On gossiping with faulty telephone lines", SIAM J .Alg. Disc. Meth., vol. 8, pp. 439-445, 1987.
T. Hasunama and H. Nagamochi, “Improved bounds for minimum fault-tolerant gossip graphs", LNCS 6986, pp. 203-214, 2011.
R. Ahlswede, L. Gargano, H. S. Haroutunian and L. H. Khachatrian, “Fault-tolerant minimum broadcast networks", NETWORKS, vol. 27, pp. 293-307, 1996.
V. H. Hovnanyan, H. E. Nahapetyan, Su. S. Poghosyan and V. S. Poghosyan, “Tighter upper bounds for the minimum number of calls and rigorous minimal time in fault-tolerant gossip schemes", arXiv:1304.5633.
Hedetniemi, Hedetniemi and Listman, “A survey of gossiping and broadcasting in communication networks", Networks, vol. 18, pp. 319-349, 1988.
D. B. West, “A class of solutions to the Gossip problem", part I, Disc. Math. vol. 39, no. 3, pp. 307-326, 1982.
D. B. West, “A class of solutions to the Gossip problem", part II, Disc. Math. vol. 40, no. 1, pp. 87-113, 1982.
D. B. West, “A class of solutions to the Gossip problem", part III, Disc. Math., vol. 40, no. 2-3, pp. 285-310, 1982.
A. Seress, “Quick Gossiping without duplicate transmissions", Graphs and Combinatorics, vol. 2, pp. 363-381, 1986.
P. Fraigniaud, A. L. Liestman, D. Soiteau, "Open problems", Parallel Processing Letters, vol. 34, pp. 507-524, 1993.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
