The minimum-length generator sequence problem is NP-hard

DOI10.1016/0196-6774(81)90029-8MaRDI QIDQ3920644zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Shimon Even, Oded Goldreich

Publication date 1981

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(81)90029-8

Mathematics Subject Classification ID

Permutation groups (20B99) Analysis of algorithms and problem complexity (68Q25)

Cited in

(30)

• Vertex reconstruction in Cayley graphs
• The complexity of finding minimum-length generator sequences
• Permutations of bounded degree generate groups of polynomial diameter
• Computing short generator sequences
• Sorting by bounded block-moves
• Edge-foreward index of star graphs and other Cayley graphs
• The optimal routing of augmented cubes
• Diameter bounds and recursive properties of Full-Flag Johnson graphs
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Cyclic group blocking polyhedra
• Approximation algorithms for sorting permutations by extreme block-interchanges
• Discrete logarithms for finite groups
• Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings
• Cryptographic hash functions and expander graphs: the end of the story?
• The time complexity of the token swapping problem and its parallel variants
• Growth in SL2 over finite fields
• A sharp diameter bound for unipotent groups of classical type over ℤ/pℤ
• The time complexity of permutation routing via matching, token swapping and a variant
• An algebraic view of bacterial genome evolution
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• scientific article; zbMATH DE number 7310266 (Why is no real title available?)
• An algorithm for computation of the growth functions in finite two-generated groups of exponent 5
• A resource-efficient algorithm for study the growth in finite two-generator groups of exponent 5
• On Applications of the Cayley Graphs of some Finite Groups of Exponent Five
• Applications of finite non-abelian simple groups to cryptography in the quantum era
• Sorting permutations by block-interchanges
• Find routes on a doughnut
• Membership problems in finite groups
• Parameterized complexity of factorization problems
• Some problems on Cayley graphs

This page was built for publication: The minimum-length generator sequence problem is NP-hard

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