Skip to content

Research at St Andrews

New refiners for permutation group search

Research output: Contribution to journalArticle

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
StateE-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. 22 Nov 2018 In : Journal of Algebra. In press

    Research output: Contribution to journalArticle

  2. Complexity of n-Queens completion (extended abstract)

    Gent, I. P., Jefferson, C. A. & Nightingale, P. W. 13 Jul 2018 Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 5608-5611 4 p.

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

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

  4. Two variants of the froidure-pin algorithm for finite semigroups

    Jonusas, J., Mitchell, J. D. & Pfeiffer, M. 8 Feb 2018 In : Portugaliae Mathematica. 74, 3, p. 173-200 28 p.

    Research output: Contribution to journalArticle

  5. Automatic discovery and exploitation of promising subproblems for tabulation

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W. & Salamon, A. Z. 2018 Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 11008)

    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