Finding a cycle base of a permutation group in polynomial time

DOI10.1016/j.jalgebra.2018.03.028zbMath1446.20009arXiv1702.05292OpenAlexW2794581491WikidataQ130048754 ScholiaQ130048754MaRDI QIDQ724293

Ilya Nikolaevich Ponomarenko, Mikhail E. Muzychuk

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)

Uses Software

• GAP

Cites Work

• Polynomial time algorithms for recognizing and isomorphism testing of cyclic tour-naments
• 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
• Black box classical groups
• Regular subgroups of primitive permutation groups
• Composition Factors from the Group Ring and Artin's Theorem on Orders of Simple Groups
• Isomorphism problem for a class of point-symmetric structures
• A solution of the isomorphism problem for circulant graphs
• Cyclic regular subgroups of primitive permutation groups
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item