Finding a cycle base of a permutation group in polynomial time

DOI10.1016/J.JALGEBRA.2018.03.028MaRDI QIDQ724293zbMATH OpenOpenAlexWikidataFDO

Authors Mikhail Muzychuk, Ilya Ponomarenko

Publication date 25 July 2018

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

Full work available at URL https://arxiv.org/abs/1702.05292

zbMATH Keywords

automorphism groupCayley graphpolynomial-time algorithmcanonical labelingcycle base

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Subgroups of symmetric groups (20B35) Computational methods for problems pertaining to group theory (20-08)

Abstract: A cycle base of a permutation group is defined to be a maximal set of its pairwise non-conjugate regular cyclic subgroups. It is proved that a cycle base of a permutation group of degree $n$ can be constructed in polynomial time in~$n$.

Recommendations

• 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

Cites work

• 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?)
• 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
• 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.

Cited in

(8)

• Recognizing circulant graphs in polynomial time: An application of association schemes
• The parameterized complexity of fixpoint free elements and bases in permutation groups
• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Testing isomorphism of circulant objects in polynomial time
• Testing isomorphism of circulant objects in polynomial time
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Finding the automorphism group of a circulant association scheme in polynomial time
• Bases of Schurian antisymmetric coherent configurations and an isomorphism test for Schurian tournaments

Describes a project that uses

Uses Software

• GAP

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)