New refiners for permutation group search

DOI10.1016/J.JSC.2017.12.003MaRDI QIDQ1757005zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Christopher Jefferson, Markus Pfeiffer, Rebecca Waldecker

Publication date 28 December 2018

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computational algebrapermutation groupsalgorithmic group theorybacktrack searchpartition backtrackrefiners

Mathematics Subject Classification ID

General theory for finite permutation groups (20B05) Computational methods for problems pertaining to group theory (20-08)

Abstract: We describe how orbital graphs can be used to improve the practical performance of many algorithms for permutation groups, including intersection and stabilizer problems. First we explain how orbital graphs can be integrated in partition backtracking, the current state of the art algorithm for many permutation group problems. We then show how our algorithms perform in practice, demonstrating improvements of several orders of magnitude for some problems.

Recommendations

• Perfect refiners for permutation group backtracking algorithms
• Computing normalizers in permutation groups
• scientific article; zbMATH DE number 1004935
• scientific article; zbMATH DE number 1849958
• Permutation group algorithms based on partitions. I: Theory and algorithms

Cites work

• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (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?)
• Permutation group algorithms based on partitions. I: Theory and algorithms
• Practical graph isomorphism. II.
• The Magma algebra system. I: The user language

Cited in

(5)

• Computing canonical images in permutation groups with graph backtracking
• On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• Perfect refiners for permutation group backtracking algorithms
• Permutation group algorithms based on directed graphs

Describes a project that uses

Uses Software

• GAP
• Magma
• nauty
• Traces
• Ferret

This page was built for publication: New refiners for permutation group search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1757005)