Algorithms for Permutation Groups and Cayley Networks
Loading...
Date
1989-09-06
Authors
Blaha, Kenneth D.
Journal Title
Journal ISSN
Volume Title
Publisher
University of Oregon
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).
Description
110 pages
Keywords
the greedy algorithm, NP-hard, abelian groups with small orbits, nonredundant bases, greedy heuristic