The minimum-length generator sequence problem is NP-hard
From MaRDI portal
Publication:3920644
DOI10.1016/0196-6774(81)90029-8zbMath0467.68046WikidataQ63628478 ScholiaQ63628478MaRDI QIDQ3920644
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
Related Items
Sorting permutations by block-interchanges, Some problems on Cayley graphs, 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, Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, Cyclic group blocking polyhedra, Discrete logarithms for finite groups, Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings, Growth in SL2 over finite fields, A sharp diameter bound for unipotent groups of classical type over ℤ/pℤ