Finding a cycle base of a permutation group in polynomial time

DOI10.1016/J.JALGEBRA.2018.03.028zbMATH Open1446.20009arXiv1702.05292OpenAlexW2794581491WikidataQ130048754 ScholiaQ130048754MaRDI QIDQ724293FDOQ724293

Ilya Ponomarenko, Mikhail Muzychuk

Publication date: 25 July 2018

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

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Regular subgroups of primitive permutation groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cyclic regular subgroups of primitive permutation groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Isomorphism problem for a class of point-symmetric structures
• A solution of the isomorphism problem for circulant graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the isomorphism problem for cyclic combinatorial objects
• 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
• Black box classical groups.
• Composition Factors from the Group Ring and Artin's Theorem on Orders of Simple Groups
• Title not available (Why is that?)
• Polynomial time algorithms for recognizing and isomorphism testing of cyclic tour-naments

Cited In (4)

• Recognizing circulant graphs in polynomial time: An application of association schemes
• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Finding the automorphism group of a circulant association scheme in polynomial time

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)