Computing canonical images in permutation groups with Graph Backtracking

Christopher Jefferson; Rebecca Waldecker; Wilf A. Wilson

doi:10.1016/j.jaca.2023.100010

Computing canonical images in permutation groups with Graph Backtracking

Christopher Jefferson
, Rebecca Waldecker (Lead / Corresponding author)
, Wilf A. Wilson

Computing

Research output: Contribution to journal › Article › peer-review

23 Downloads (Pure)

Abstract

We describe a new algorithm for finding a canonical image of an object under the action of a finite permutation group. This algorithm builds on previous work using Graph Backtracking [9], which extends Jeffrey Leon's Partition Backtrack framework [14], [15]. Our methods generalise both Nauty [17] and Steve Linton's Minimal image algorithm [16].

Original language	English
Article number	100010
Number of pages	11
Journal	Journal of Computational Algebra
Volume	8
Early online date	4 Oct 2023
DOIs	https://doi.org/10.1016/j.jaca.2023.100010
Publication status	Published - Dec 2023

Access to Document

10.1016/j.jaca.2023.100010Licence: CC BY

Final published versionFinal published version, 500 KBLicence: CC BY

Cite this

@article{541998121d3a4cabbd83332d599a9721,

title = "Computing canonical images in permutation groups with Graph Backtracking",

abstract = "We describe a new algorithm for finding a canonical image of an object under the action of a finite permutation group. This algorithm builds on previous work using Graph Backtracking [9], which extends Jeffrey Leon's Partition Backtrack framework [14], [15]. Our methods generalise both Nauty [17] and Steve Linton's Minimal image algorithm [16].",

author = "Christopher Jefferson and Rebecca Waldecker and Wilson, \{Wilf A.\}",

year = "2023",

month = dec,

doi = "10.1016/j.jaca.2023.100010",

language = "English",

volume = "8",

}

TY - JOUR

T1 - Computing canonical images in permutation groups with Graph Backtracking

AU - Jefferson, Christopher

AU - Waldecker, Rebecca

AU - Wilson, Wilf A.

PY - 2023/12

Y1 - 2023/12

N2 - We describe a new algorithm for finding a canonical image of an object under the action of a finite permutation group. This algorithm builds on previous work using Graph Backtracking [9], which extends Jeffrey Leon's Partition Backtrack framework [14], [15]. Our methods generalise both Nauty [17] and Steve Linton's Minimal image algorithm [16].

AB - We describe a new algorithm for finding a canonical image of an object under the action of a finite permutation group. This algorithm builds on previous work using Graph Backtracking [9], which extends Jeffrey Leon's Partition Backtrack framework [14], [15]. Our methods generalise both Nauty [17] and Steve Linton's Minimal image algorithm [16].

U2 - 10.1016/j.jaca.2023.100010

DO - 10.1016/j.jaca.2023.100010

M3 - Article

VL - 8

JO - Journal of Computational Algebra

JF - Journal of Computational Algebra

M1 - 100010

ER -

Computing canonical images in permutation groups with Graph Backtracking

Abstract

Access to Document

Fingerprint

Cite this