Skip to content

Research at St Andrews

New refiners for permutation group search

Research output: Contribution to journalArticle

Author(s)

Christopher Jefferson, Markus Pfeiffer, Rebecca Waldecker

School/Research organisations

Abstract

Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack – in some cases by several orders of magnitude.
Close

Details

Original languageEnglish
Pages (from-to)70-92
Number of pages23
JournalJournal of Symbolic Computation
Volume92
Early online date11 Jan 2018
DOIs
Publication statusPublished - May 2019

    Research areas

  • Backtrack search, Refiners, Permutation groups, Algorithmic group theory, Computational algebra, Partition backtrack

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Athanor: high-level local search over abstract constraint specifications in Essence

    Attieh, S., Dang, N., Jefferson, C., Miguel, I. & Nightingale, P., 10 Aug 2019, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1056-1063

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. GAP – Groups, Algorithms, and Programming, Version 4.10.2

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 19 Jun 2019

    Research output: Non-textual formSoftware

  3. Minimal and canonical images

    Jefferson, C., Jonauskyte, E., Pfeiffer, M. & Waldecker, R., 1 Mar 2019, In : Journal of Algebra. 521, p. 481-506

    Research output: Contribution to journalArticle

  4. GAP – Groups, Algorithms, and Programming, Version 4.10.1

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 23 Feb 2019

    Research output: Non-textual formSoftware

  5. GAP – Groups, Algorithms, and Programming, Version 4.10.0

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 1 Nov 2018

    Research output: Non-textual formSoftware

Related by journal

  1. Computing finite semigroups

    East, J., Egri-Nagy, A., Mitchell, J. D. & Péresse, Y., 14 Feb 2018, In : Journal of Symbolic Computation. 45 p.

    Research output: Contribution to journalArticle

  2. Integrality and arithmeticity of solvable linear groups

    Detinko, A., Flannery, D. & de Graaf, W., 2015, In : Journal of Symbolic Computation. 68, p. 138–145

    Research output: Contribution to journalArticle

  3. Easy Composition of Symbolic Computation Software using SCSCP: A New Lingua Franca for Symbolic Computation

    Linton, S. A., Hammond, K., Konovalov, A., Brown, C. M., Trinder, P. W., Loidl, H-W., Horn, P. & Roozemond, D., Feb 2013, In : Journal of Symbolic Computation. 49, p. 95-119 15 p.

    Research output: Contribution to journalArticle

  4. Constructive homomorphisms for classical groups

    Murray, S. H. & Roney-Dougal, C. M., Apr 2011, In : Journal of Symbolic Computation. 46, 4, p. 371-384

    Research output: Contribution to journalArticle

ID: 245468143