Skip to content

Research at St Andrews

New refiners for permutation group search

Research output: Contribution to journalArticlepeer-review

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. Strong external difference families in abelian and non-abelian groups

    Huczynska, S., Jefferson, C. & Nepšinská, S., 8 Feb 2021, In: Cryptography and Communications . First Online, 11 p.

    Research output: Contribution to journalArticlepeer-review

  2. 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 (IJCAI-19). Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1056-1063 8 p.

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

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

  4. 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 journalArticlepeer-review

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

Related by journal

  1. Lifting tropical bitangents

    Len, Y. & Markwig, H., Jan 2020, In: Journal of Symbolic Computation. 96, p. 122-152

    Research output: Contribution to journalArticlepeer-review

  2. Polynomial-time proofs that groups are hyperbolic

    Holt, D., Linton, S., Neunhoeffer, M., Parker, R., Pfeiffer, M. & Roney-Dougal, C. M., May 2021, In: Journal of Symbolic Computation. 104, p. 419-475

    Research output: Contribution to journalArticlepeer-review

  3. Computing finite semigroups

    East, J., Egri-Nagy, A., Mitchell, J. D. & Péresse, Y., May 2019, In: Journal of Symbolic Computation. 92, p. 110-155 46 p.

    Research output: Contribution to journalArticlepeer-review

  4. 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 journalArticlepeer-review

ID: 245468143

Top