Bases, subgroup towers and strong genera.ting sets (SGSs) have played a. key role in the development of algorithms for permutation groups. We analyze the computational complexity of several problems involving bases and SGSs, and we use subgroup towers and SGSs to construct dense networks with practical routing schemes.

Given generators for G ≤ Sym(n), we prove that the problem of computing a minimum base for G is NP-hard. In fact, the problem is NP-hard for cyclic groups and elementary abelian groups. However for abelian groups with orbits of size less than 8, a. polynomial time algorithm is presented for computing minimum bases.

For arbitrary permutation groups a greedy algorithm for approximating minimum bases is investigated. We prove that if G ≤ Sym(n) with a minimum base of size k, then the greedy algorithm produces a base of size Ω(k log log n).

We show that the decision analogs to the following two algebraic problems are LOGSPACE-complete for P: computing a greedy base for G ≤ Sym(n), and "sifting" σ ∈ G through an arbitrary SGS for G. In contrast, we prove that for any polynomial subgroup tower of a solvable group one can find an SGS for which sifting is in NC.

Because of their inherent symmetry Cayley graphs are an attractive model for parallel processing networks. Unfortunately, Jerrum has shown that computing a minimal route for an arbitrary Cayley graph is PSPACE-complete.

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.