Please use this identifier to cite or link to this item:
Title: Permutation group algorithms based on directed graphs
Author(s): Jefferson, Christopher
Pfeiffer, Markus
Wilson, Wilf A.
Waldecker, RebeccaLook up in the Integrated Authority File of the German National Library
Issue Date: 2021
Type: Article
Language: English
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 GraphBacktracking package for GAP.
Open Access: Open access publication
License: (CC BY 4.0) Creative Commons Attribution 4.0(CC BY 4.0) Creative Commons Attribution 4.0
Sponsor/Funder: Publikationsfonds MLU
Journal Title: Journal of algebra
Publisher: Elsevier
Publisher Place: San Diego, Calif.
Volume: 585
Original Publication: 10.1016/j.jalgebra.2021.06.015
Page Start: 723
Page End: 758
Appears in Collections:Open Access Publikationen der MLU

Files in This Item:
File Description SizeFormat 
1-s2.0-S0021869321003240-main.pdf743.12 kBAdobe PDFThumbnail