New refiners for permutation group search

DOI10.1016/J.JSC.2017.12.003zbMATH Open1502.20002DBLPjournals/jsc/JeffersonPW19arXiv1608.08489OpenAlexW2963517760WikidataQ57990349 ScholiaQ57990349MaRDI QIDQ1757005FDOQ1757005

Authors: Christopher Jefferson, Markus Pfeiffer, Rebecca Waldecker 

Publication date: 28 December 2018

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

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.

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

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

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)

Cites Work

• The Magma algebra system. I: The user language
• Practical graph isomorphism. II.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Permutation group algorithms based on partitions. I: Theory and algorithms

Cited In (5)

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

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)