Computing short generator sequences

DOI10.1016/0890-5401(87)90043-5zbMath0621.20016OpenAlexW2032908207MaRDI QIDQ1090414

Merrick L. Furst, James R. Driscoll

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90043-5

zbMATH Keywords

presentationCayley graphcomputer algebrapolynomial algorithmsdiameter of the permutation groupfinite set of permutations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Software, source code, etc. for problems pertaining to group theory (20-04) Subgroups of symmetric groups (20B35) Algorithms in computer science (68W99)

Related Items

On Random Walks in Large Compact Lie Groups ⋮ Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement ⋮ On the diameter of Cayley graphs of the symmetric group ⋮ Growth in SL2 over finite fields ⋮ On the diameter of permutation groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of finding minimum-length generator sequences
• Permutations of bounded degree generate groups of polynomial diameter
• The minimum-length generator sequence problem is NP-hard