Minimal and Canonical Images

2017/03/01 by Jefferson, Christopher, Jonauskyte, Eliza, Pfeiffer, Markus +1 · 1 citation
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1703.00197

Abstract

We describe a family of new algorithms for finding the canonical image of a set of points under the action of a permutation group. This family of algorithms makes use of the orbit structure of the group, and a chain of subgroups of the group, to efficiently reduce the amount of search which must be performed to find a canonical image. We present both a formal proof of correctness of our algorithms and experiments on different permutation groups, which compare our algorithms with the previous state of the art.

Cited by

• The lattice packing problem in dimension 9 by Voronoi's algorithm

Related

• Computing canonical images in permutation groups with Graph Backtracking
• Separating subsets from their images
• Finite Permutation Groups with Few Orbits Under the Action on the Power Set
• Generating tuples of integers modulo the action of a permutation group and applications
• A method for building permutation representations of finitely presented\n groups