Algorithms for Permutation Groups and Cayley Networks
Kenneth D. Blaha
Committee: Eugene M. Luks
Technical Report(Sep 1989)
Keywords:

We use subgroup towers and SGSs to construct Cayley networks with "failsoft" routing algorithms, and we adapt Valiant's permutation, routingĀ· algorithm to run on the directed Cayley networks. Normal towers are used to define Cayley graphs and routing algorithms that perform well, as long no more than d-1 processors fail (d the degree of the graph). For several Cayley network families we exhibit a universal broadcast algorithm that runs in optimal time.

These same techniques are used to analyze nonsymmetric networks. In particular, we prove that Leland and Solomon's moebius graph is isomorphic to a quotient Cayley graph. This information is used to efficiently compute minimum routes and determine the diameter of the moebius graph.