Method of Local Interchange for the Investigation of Gossip Problems: part 2
Keywords:
Graphs, Networks, Telephone problem, Gossip problemAbstract
The method of construction of Gossip graphs providing a full information exchange with minimal number of calls in minimum time is described. The basis for the graphs of the presented class is the subgraph of canonical form obtained from NOHO graphs by applying the operation of local interchange on them developed by us in.
References
T. Tijdeman, “On a telephone problem", Nieuw Archief voor Wiskunde, vol. 3, pp. 188-192, 1971.
B.Baker and R.Shostak, “Gossips and telephones", Discrete Mathematics, vol. 2, pp. 191-193, 1972.
R.T. Bumby, “A problem with telephones", SIAM Journal on Algebraic Discrete Methods, vol. 2, pp. 13-18, 1981.
A. Hajnal, E.C. Milner and E. Szemeredi, “A cure for the telephone disease", Canadian Mathematical Bulletin., vol. 15, pp. 447-450, 1972.
A. Seress, “Quick gossiping by conference calls", SIAM Journal on Discrete Mathematics, vol. 1, pp. 109-120, 1988.
D.B. West, “Gossiping without duplicate transmissions", SIAM Journal on Algebraic Discrete Methods, vol. 3, pp. 418-419, 1982.
G. Fertin and A. Respaud, "A survey on Knödel graphs", Discrete Applied Mathematics, vol. 137, no. 2, pp. 173-195, 2003.
R. Labahn, “Kernels of minimum size gossip schemes", Discrete Mathematics, 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.
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 Journal on Algebraic Discrete Methods, vol. 7, pp. 13-17, 1987.
R.W. Haddad, S. Roy and A .A. Schaffer, “On gossiping with faulty telephone lines", SIAM Journal on Algebraic Discrete Methods, vol. 8, pp. 439-445, 1987.
T. Hasunama and H. Nagamochi, “Improved bounds for minimum fault-tolerant gossip graphs", Lecture Notes in Computer Science, vol. 6986, pp. 203-214, 2011.
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.
A. Bavelas, “Communication pattern in task-oriented groups", Journal of the Acoustical Society of America vol. 22, pp. 725-730, 1950.
W. Knodel, “New gossips and telephones", Discrete Mathematics, vol. 13, pp. 95, 1975.
S. M. Hedetniemi, S. T. Hedetniemi, A. L. Liestman, A survey of gossiping and broadcasting in communication networks", Networks, vol. 18, pp. 319-349, 1988.
V. H. Hovnanyan, Su. S. Poghosyan and V. S. Poghosyan, “Method of local interchange to investigate Gossip problems", Transactions of IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 40, pp. 5-12, 2013.
D. B. West, “A class of solutions to the gossip problem", part I, Discrete Mathematics, vol. 39, no. 3, pp. 307-326, 1982
J. Nieminen, “Time and call limited telephone problems", IEEE Transactions on Circuits and Systems, vol. 34, pp. 1129-1131, 1987.
A. Seress, “Quick Gossiping without duplicate transmissions", Graphs and Combinatorics, vol. 2, pp. 363-381, 1986.
P. Fraigniaud, A. L. Liestman and D. Soiteau, “Open problems", Parallel Processing Letters, vol. 3, no. 4, pp. 507-524, 1993.
A. Pelc, “Fault-tolerant broadcasting and gossiping in communication networks", Networks, vol. 28, pp. 143-156, 1996.
R. Ahlswede, L. Gargano, H. S. Haroutunian and L. H. Khachatrian, “Fault-tolerant minimum broadcast networks", Networks, vol. 27, pp. 293-307, 1996.
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, Discrete Mathematics, vol. 40, no. 2-3, pp. 285-310, 1982.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
