Computing short generator sequences

DOI10.1016/0890-5401(87)90043-5MaRDI QIDQ1090414zbMATH OpenOpenAlexFDO

Authors Merrick 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

Cayley graphcomputer algebradiameter of the permutation groupfinite set of permutationspolynomial algorithmspresentation

Mathematics Subject Classification ID

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) Generators, relations, and presentations of groups (20F05) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Review text

Let P be a finite set of permutations of n letters. The diameter of the permutation group \(G=

\) (with respect to P) is by definition the least integer k such that every permutation in G can be expressed as a product of at most k elements of P. This concept corresponds to the diameter of the Cayley graph associated to the given presentation of G. It is shown in the paper that the diameter of a permutation group G generated by a set P of cycles of bounded degree is \(O(n^ 2)\). This bound is best possible. In addition, it is shown that such short products can be found in polynomial time. The techniques presented in the paper may be applied to various well known permutation-group puzzles.

Recommendations

• Permutations of bounded degree generate groups of polynomial diameter
• scientific article; zbMATH DE number 3900155
• scientific article; zbMATH DE number 1245638
• On the diameter of the symmetric group: polynomial bounds.
• On the diameter of permutation groups

Cites work

• scientific article; zbMATH DE number 3137403 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• scientific article; zbMATH DE number 3341276 (Why is no real title available?)
• Permutations of bounded degree generate groups of polynomial diameter
• The complexity of finding minimum-length generator sequences
• The minimum-length generator sequence problem is NP-hard

Cited in

(10)

• Permutations of bounded degree generate groups of polynomial diameter
• On the diameter of Cayley graphs of the symmetric group
• On the diameter of permutation groups
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Growth in SL2 over finite fields
• The lower bound of diameter of alternating groups
• scientific article; zbMATH DE number 3900155 (Why is no real title available?)
• scientific article; zbMATH DE number 1245638 (Why is no real title available?)
• On random walks in large compact Lie groups
• A new strategy for generating shortest addition sequences

This page was built for publication: Computing short generator sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090414)