Gossiping in circulant graphs

• Romain Gay ^[1]
  1. [1] ENS Cachan, Paris
• Localización: Reports@SCM: an electronic journal of the Societat Catalana de Matemàtiques, ISSN-e 2385-4227, Vol. 1, Nº. 1, 2014, págs. 39-53
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen
  • català

    Investiguem el problema de fer safareig, en el qual els nodes d'una xarxad'intercomunicació comparteixen informació mitjançant un protocol de comunicació per rondes. Considerem dos tipus de protocols: per rutes disjuntes en vèrtexs, i per rutes disjuntes en arestes. Donem una ta inferior general per la complexitat dels algoritmes de xafarderies en termes de la funció isoperimètrica de la xarxa. Ens centrem en els grafs de Cayley i donem algorismes òptims per subclasses de grafs de Cayley i, en particular, pels grafs circulants.

  • English

    We investigate the gossiping problem, in which nodes of an intercommunication network share information initially given to each one of them according to a communication protocol by rounds. We consider two types of communication protocols: vertex-disjoint path mode, and edge-disjoint path mode. We give a general lower bound on the complexity of gossiping algorithms in terms of the isoperimetric function of the graph. We focus on Cayley graphs and give optimal algorithms for subclasses of Cayley graphs and, in particular, for circulant graphs. Keywords: Gossiping, isoperimetric function, Cayley graphs, circulantgraphs, cube. MSC (2010): 05C85, 68R10.

• Referencias bibliográficas
  • B. Baker and R. Shostak. Gossips and telephones.Discrete Mathematics, 2:191–193,1972.
  • S. Even and B. Monien. On the Number ofRounds Necessary to Disseminate Information (Extended Abstract). InFirst ACM Symposium...
  • Uriel Feige, David Peleg, Prabhakar Raghavan,and Eli Upfal. Randomized broadcast in net-works. Random Struct. Algorithms, 1(4):447–460,...
  • R. Feldmann,J. Hromkovic,B. Monien,S. Madhavapeddy, and P. Mysliwietz .Optimal algorithms for dissemination of information in...
  • A.M. Frieze and G.R. Grimmett. The shortest path problem for graphs with random arc lengths. Discrete Applied Mathematics, 10:57–77,...
  • R. Gay. Gossiping in Cayley graphs. Technical report, ENS Cachan, France, 2013.
  • J. Hromkovic, R. Klasing, and E.A. Stohr. Dissemination of information in vertex-disjoint paths mode. Computers and Artificial...
  • J. Hromkovic, R. Klasing, E.A. Stohr, and H. Wagener. Gossiping in vertex disjoint paths mode in d-dimensional grids and...
  • J. Hromkovic, R. Klasing, W. Unger, andH. Wagener. Optimal algorithms for broadcastand gossip in the edge-disjoint path modes...
  • Ralf Klasing. The relationship between gossiping in vertex-disjoint paths mode and bisection width. Discrete Applied Mathematics, 83(1-3):229–246,...
  • W. Knodel. New gossips and telephones. Discrete Mathematics, 13:95, 1975.
  • P. Kolman.Searching for Edge Disjoint Pathson Hypercube-like Topologies. PhD thesis, Faculty of Mathematics and Physics Charles...
  • D. W. Krumme, G. Cybenko, and K. N. Venkataraman. Gossiping in minimal time. SIAM J. on Computing, 21:111–139, 1992.
  • R. Labahn and I. Warnke. Quick gossiping by telegraphs. Discrete Mathematics, 126:421–424, 1994.
  • B. Mans and I. E. Shparlinski. Random walksand bisections in random circulant graphs. LATIN, pages 542–555, 2012.