Finding a cycle base of a permutation group in polynomial time
A cycle base \(B\) of a permutation group \(K\leq\mathrm{Sym}(n)\) is a set of representatives of the conjugacy classes of regular cyclic subgroups \(G\) of \(K\). In earlier papers the authors have described efficient algorithms in recognition and isomorphism testing of circulant graphs under the hypothesis that cycle bases are given (see [\textit{S. A. Evdokimov} and the second author, St. Petersbg. Math. J. 15, No. 6, 813--835 (2004; Zbl 1061.05045); translation from Algebra Anal. 15, No. 6, 1--34 (2003)] and [the first author, Proc. Lond. Math. Soc. (3) 88, No. 1, 1--41 (2004; Zbl 1045.05052)]). In the present paper, they show that there exists a \(\mathrm{poly}(n)\) algorithm to construct a cycle base for a subgroup of \(\mathrm{Sym}(n)\) defined by a generating set whose size is polynomial in \(n\). The major step to prove this result depends on showing that there exists a \(\mathrm{poly}(n)\) algorithm to construct a solvable subgroup \(K_{0}\leq K\) such that every regular cyclic subgroup of \(K\) is \(K\)-conjugate to a subgroup of \(K_{0}\). In particular, it follows that, given a combinatorial object \(X\) on \(n\) points and its automorphism group \(\mathrm{Aut}(X)\), it is possible to decide whether \(X\) is a circulant object in time \(\mathrm{poly}(n)\); if so, a complete system of pairwise nonequivalent circulant representations of \(X\) can be constructed.
- Circulant graphs: recognizing and isomorphism testing in polynomial time
- Recognizing and testing isomorphism of Cayley graphs over an abelian group of order \(4p\) in polynomial time
- Finding the automorphism group of a circulant association scheme in polynomial time
- Polynomial time recognition and isomorphism testing for cyclic tournaments
- Testing isomorphism of circulant objects in polynomial time
- A black-box group algorithm for recognizing finite symmetric and alternating groups, I
- Recognizing circulant graphs in polynomial time: An application of association schemes
- Identifying long cycles in finite alternating and symmetric groups acting on subsets
- Economical generating sets for the symmetric and alternating groups consisting of cycles of a fixed length.
- On natural isomorphisms of cycle permutation graphs
- A solution of the isomorphism problem for circulant graphs
- Black box classical groups.
- Composition Factors from the Group Ring and Artin's Theorem on Orders of Simple Groups
- Cyclic regular subgroups of primitive permutation groups
- scientific article; zbMATH DE number 3710402 (Why is no real title available?)
- scientific article; zbMATH DE number 3771876 (Why is no real title available?)
- scientific article; zbMATH DE number 3496414 (Why is no real title available?)
- scientific article; zbMATH DE number 475362 (Why is no real title available?)
- scientific article; zbMATH DE number 1849958 (Why is no real title available?)
- scientific article; zbMATH DE number 894528 (Why is no real title available?)
- scientific article; zbMATH DE number 3223737 (Why is no real title available?)
- scientific article; zbMATH DE number 3070465 (Why is no real title available?)
- Isomorphism problem for a class of point-symmetric structures
- On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
- On the isomorphism problem for cyclic combinatorial objects
- Polynomial time algorithms for recognizing and isomorphism testing of cyclic tour-naments
- Regular subgroups of primitive permutation groups.
- On the isomorphism problem for cyclic combinatorial objects
- Testing isomorphism of circulant objects in polynomial time
- The parameterized complexity of fixpoint free elements and bases in permutation groups
- Finding the automorphism group of a circulant association scheme in polynomial time
- Polynomial time recognition and isomorphism testing for cyclic tournaments
- Bases of Schurian antisymmetric coherent configurations and an isomorphism test for Schurian tournaments
- Circulant graphs: recognizing and isomorphism testing in polynomial time
- Recognizing circulant graphs in polynomial time: An application of association schemes
- Testing isomorphism of circulant objects in polynomial time
This page was built for publication: Finding a cycle base of a permutation group in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q724293)
