Algorithms for Permutation Groups and Cayley Networks
| dc.contributor.author | Blaha, Kenneth D. | |
| dc.date.accessioned | 2023-06-14T22:27:07Z | |
| dc.date.available | 2023-06-14T22:27:07Z | |
| dc.date.issued | 1989-09-06 | |
| dc.description | 110 pages | en_US |
| dc.description.abstract | Bases, 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). | en_US |
| dc.identifier.uri | https://hdl.handle.net/1794/28417 | |
| dc.language.iso | en | en_US |
| dc.publisher | University of Oregon | en_US |
| dc.rights | Creative Commons BY-NC-ND 4.0-US | en_US |
| dc.subject | the greedy algorithm | en_US |
| dc.subject | NP-hard | en_US |
| dc.subject | abelian groups with small orbits | en_US |
| dc.subject | nonredundant bases | en_US |
| dc.subject | greedy heuristic | en_US |
| dc.title | Algorithms for Permutation Groups and Cayley Networks | en_US |
| dc.type | Thesis / Dissertation | en_US |