Gossiping in circulant graphs
Keywords:
Gossiping, isoperimetric function, Cayley graphs, circulant graphs, cube. MSC (2010), 05C85, 68R10.Abstract
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, circulant
graphs, cube. MSC (2010): 05C85, 68R10.
Downloads
Downloads
How to Cite
Issue
Section
License
- Authors assign to Societat Catalana de Matemàtiques (a subsidiary of Institut d’Estudis Catalans) the rights of reproduction, communication to the public and distribution of the articles submitted for publication to Reports@SCM.
- Authors answer to Societat Catalana de Matemàtiques for the authorship and originality of submitted articles.
- Authors are responsible for obtaining permission for the reproduction of all graphic material included in articles.
- Societat Catalana de Matemàtiques declines all liability for the possible infringement of intellectual property rights by authors.
- The contents published in the journal, unless otherwise stated in the text or in the graphic material, are subject to a Creative Commons Attribution-NonCommercial-NoDerivs (by-nc-nd) 3.0 Spain licence, the complete text of which may be found at https://creativecommons.org/licenses/by-nc-nd/3.0/es/deed.en. Consequently, the general public is authorised to reproduce, distribute and communicate the work, provided that its authorship and the body publishing it are acknowledged, and that no commercial use and no derivative works are made of it.
- The journal Reports@SCM is not responsible for the ideas and opinions expressed by the authors of the published articles.