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 statusE-pub ahead of print - 11 Jan 2018

    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. 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

  2. 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

  3. 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

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

    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., 5 Sep 2018

    Research output: Non-textual formSoftware

  5. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P., 13 Jul 2018, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

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

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