A Class of Arc-Transitive Cayley Graphs as Models for Interconnection Networks
Sanming Zhou
Source abstract
We study a class of Cayley graphs as models for interconnection networks. With focus on efficient communication we prove that for any graph in the class there exists a gossiping protocol which exhibits attractive features, and, moreover, we give an algorithm for constructing such a protocol. In particular, these hold for two important subclasses of graphs, namely, Cayley graphs admitting a complete rotation and Frobenius graphs of a certain type. For such Frobenius graphs, we obtain the minimum gossip time and give an optimal gossiping protocol under which messages are transmitted along shortest paths and each arc is used exactly once at each time step. Moreover, for such Frobenius graphs we construct an all-to-all shortest path routing that is arc-transitive, edge- and arc-uniform, and optimal for the edge- and arc-forwarding indices simultaneously.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.