New refiners for permutation group search. (May 2019)

• Record Type: Journal Article
• Authors: Jefferson, Christopher; Pfeiffer, Markus; Waldecker, Rebecca
• Is Part Of: Journal of symbolic computation. Volume 92(2019)
• Page Start: 70
• Page End: 92
• Publication Date: 2019-05
• Subjects: Backtrack search -- Refiners -- Permutation groups -- Algorithmic group theory -- Computational algebra -- Partition backtrack; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.12.003
• Languages: English
• ISSNs: 0747-7171

Abstract

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.