Chennai Mathematical Institute

Seminars




10.30 a.m.
Two classes of network structures that enable efficient information transmission

Prof. Sanming Zhou
University of Melbourne, Australia.
11-12-12


Abstract

What network topologies should we use in order to achieve efficient information transmission? Of course answer to this question depends on how we measure efficiency of information dissemination. If we measure it by the minimum gossiping time under the store-and-forward, all-port and full-duplex model, we show that certain Cayley graphs associated with Frobenius groups are `perfect' in a sense. (A Frobenius group is a permutation group which is transitive but not regular such that only the identity element can fix two points.) Such graphs are also optimal for all-to-all routing in the sense that the maximum load on edges achieves the minimum. In this talk we will discuss this theory of optimal network design.