Method of Local Interchange to Investigate Gossip Problems

Authors

  • Vilyam H. Hovnanyan Institute for Informatics and Automation Problems of NAS RA
  • Suren S. Poghosyan Institute for Informatics and Automation Problems of NAS RA
  • Vahagn S. Poghosyan Institute for Informatics and Automation Problems of NAS RA

Keywords:

Graphs, Networks, Telephone problem, Gossip problem

Abstract

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

2021-12-10

How to Cite

Hovnanyan, V. H., Poghosyan, S. S., & Poghosyan, V. S. (2021). Method of Local Interchange to Investigate Gossip Problems. Mathematical Problems of Computer Science, 40, 5–12. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/243