𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Algorithm for Solving the Factorization Problem in Permutation Groups

✍ Scribed by T. Minkwitz

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
345 KB
Volume
26
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

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, the problem can be solved from a strong generating set (SGS) and a base of G. Different algorithms to compute an SGS and a base have been published. The classical algorithm is the Schreier-Sims method. However, for factorization an SGS is needed that has all its elements represented as words over S. The existing methods are not suitable, because they lead to an exponential growth of word lengths. This article presents a simple algorithm to solve the factorization problem. It is based on computing an SGS with elements represented by relatively short words over the generators.

πŸ“œ SIMILAR VOLUMES

A New Algorithm for Solving the Word Pro
A New Algorithm for Solving the Word Problem in Braid Groups
✍ D. Garber; S. Kaplan; M. Teicher πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 148 KB

One of the most interesting questions about a group is whether its word problem can be solved and how. The word problem in the braid group is of particular interest to topologists, algebraists, and geometers, and is the target of intensive current research. We look at the braid group from a topologi

An algebraic multigrid wave–ray algorith
An algebraic multigrid wave–ray algorithm to solve eigenvalue problems for the helmholtz operator
✍ Irene Livshits πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 112 KB

## Abstract Helmholtz equations with variable coefficients are known to be hard to solve both analytically and numerically. In this paper, we introduce a numerical multigrid solver for one‐dimensional Helmholtz eigenvalue problems with periodic potentials and solutions. The solvers employ wave–ray

A branch-and-cut algorithm for solving a
A branch-and-cut algorithm for solving an intraring synchronous optical network design problem
✍ Lee, Youngho; Sherali, Hanif D.; Han, Junghee; Kim, Seong-in πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 133 KB πŸ‘ 2 views

In this paper, we deal with a network design problem arising from the deployment of synchronous optical networks (SONET), a standard of transmission using optical fiber technology. The problem is to find an optimal clustering of traffic demands in the network such that the total number of node assig

An Efficient Algorithm for Solving the I
An Efficient Algorithm for Solving the Inverse Problem of Locating the Interfaces Using the Frequency Sounding Data
✍ Alexandre Timonov; Michael V. Klibanov πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 146 KB

We consider the inverse coefficient problem of locating the interface positions arising in frequency sounding of layered media. Such a problem is of particular interest in the exploration of geophysics, underwater acoustics and electromagnetics, optical sensing, and so forth. We found that a simplif