Blaha, Kenneth D.2023-06-142023-06-141989-09-06https://hdl.handle.net/1794/28417110 pagesBases, subgroup towers and strong generating 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).enCreative Commons BY-NC-ND 4.0-USthe greedy algorithmNP-hardabelian groups with small orbitsnonredundant basesgreedy heuristicThesis / Dissertation