Nearly linear time algorithms for permutation groups: An interplay between theory and practice
This paper contains a nice survey of permutation group algorithms, concentrating on those which are polynomial time but also mentioning some which are not. The focus is on asymptotic analysis but practical implementations are mentioned also. This paper emphasizes ``nearly linear time algorithms, that is, those whose time bound is \(O(n\log^c| G|)\) for a permutation group \(G\) of degree \(n\). (In the important case of small-base groups this time bound is linear except for factors of \(\log n\).) After surveying several existing algorithms, the author presents some new nearly linear time algorithms (building on previous methods), culminating in one for finding the upper central series of a nilpotent group. This new algorithm is deterministic, unlike many other nearly linear time algorithms.
- Some algorithms for nilpotent permutation groups
- scientific article; zbMATH DE number 434875 (Why is no real title available?)
- scientific article; zbMATH DE number 1254260 (Why is no real title available?)
- scientific article; zbMATH DE number 1273663 (Why is no real title available?)
- scientific article; zbMATH DE number 1004940 (Why is no real title available?)
- Normalisers of primitive permutation groups in quasipolynomial time
This page was built for publication: Nearly linear time algorithms for permutation groups: An interplay between theory and practice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1270640)
