𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some Algorithms for Nilpotent Permutation Groups

✍ Scribed by Eugene M. Luks; Ferenc Rákóczi; Charles R.B. Wright

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
727 KB
Volume
23
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

Let G, H and E be subgroups of a finite nilpotent permutation group of degree n. We describe the theory and implementation of an algorithm to compute the normalizer N G (H) in time polynomial in n, and we give a modified algorithm to determine whether H and E are conjugate under G and, if so, to find a conjugating element of G. Other algorithms produce the intersection G ∩ H and the centralizer C G (H). The underlying method uses the imprimitivity structure of G, H and an associated canonical chief series to reduce computation to linear operations. Implementations in GAP and Magma are practical for degrees large enough to present difficulties for general-purpose methods.

📜 SIMILAR VOLUMES

A Random Base Change Algorithm for Permu
A Random Base Change Algorithm for Permutation Groups
✍ Gene Cooperman; Larry Finkelstein 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 549 KB

A new random base change algorithm is presented for a permutation group \(G\) acting on \(n\) points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random ge

Efficient Parallel Algorithms for Permut
Efficient Parallel Algorithms for Permutation Graphs
✍ K. Arvind; V. Kamakoti; C.P. Rangan 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 641 KB

In this paper, we present optimal \(O(\log n)\) time, \(O(n / \log n)\) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an \(O(\log n)\) time, \(O(n)\) processor, CREW PRAM model parallel algorithm for fi

An Algorithm for Solving the Factorizati
An Algorithm for Solving the Factorization Problem in Permutation Groups
✍ T. Minkwitz 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 345 KB

The factorization problem in permutation groups is to represent an element g of some permutation group G as a word over a given set S of generators of G. For practical purposes, the word should be as short as possible, but must not be minimal. Like many other problems in computational group theory,