Permutation group algorithms based on directed graphs

Christopher Jefferson, Markus Pfeiffer, Wilf A Wilson, Rebecca Waldecker*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce a new framework for solving an important class of computational problems involving finite permutation groups, which includes calculating set stabilisers, intersections of subgroups, and isomorphisms of combinatorial structures. Our techniques are inspired by and generalise 'partition backtrack', which is the current state-of-the-art algorithm introduced by Jeffrey Leon in 1991. But, instead of ordered partitions, we use labelled directed graphs to organise our backtrack search algorithms, which allows for a richer representation of many problems while often resulting in smaller search spaces. In this article we present the theory underpinning our framework, we describe our algorithms, and we show the results of some experiments. An implementation of our algorithms is available as free software in the Graph Back tracking package for GAP.
Original languageEnglish
Pages (from-to)723-758
Number of pages36
JournalJournal of Algebra
Volume585
Early online date29 Jun 2021
DOIs
Publication statusPublished - 1 Nov 2021

Fingerprint

Dive into the research topics of 'Permutation group algorithms based on directed graphs'. Together they form a unique fingerprint.

Cite this