𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A New Algorithm for Solving the Word Problem in Braid Groups

✍ Scribed by D. Garber; S. Kaplan; M. Teicher

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
148 KB
Volume
167
Category
Article
ISSN
0001-8708

No coin nor oath required. For personal study only.

✦ Synopsis

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 topological point of view (rather than a geometric one). The braid group is defined by the action of diffeomorphisms on the fundamental group of a punctured disk. We exploit the topological definition in order to give a new approach for solving its word problem. Our algorithm, although not better in complexity, is faster in comparison with known algorithms for short braid words, and it is almost independent of the number of strings in the braids. Moreover, the algorithm is based on a new computer presentation of the elements of the fundamental group of a punctured disk. This presentation can be used also for other algorithms.

πŸ“œ SIMILAR VOLUMES

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,

A Polylogarithmic Approximation Algorith
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
✍ Naveen Garg; Goran Konjevod; R. Ravi πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 130 KB

The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group.The problem was introduced by Reich a

A branch-and-cut algorithm for solving g
A branch-and-cut algorithm for solving generalized multiperiod Steiner problems in graphs
✍ Suhl, Uwe H.; Hilbert, Heinrich πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 163 KB πŸ‘ 2 views

Given is an undirected graph with positive or negative edge weights which represent a profit if an investment such as installing a gas pipe takes place in a given time period. A certain part of the graph may already be piped in previous periods. The task is to extend the piped subgraph in the most p

Application of the Lanczos algorithm for
Application of the Lanczos algorithm for solving the linear systems that occur in continuation problems
✍ C.-S. Chien; S.-L. Chang πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 166 KB

## Abstract We study the Lanczos method for solving symmetric linear systems with multiple right‐hand sides. First, we propose a numerical method of implementing the Lanczos method, which can provide all approximations to the solution vectors of the remaining linear systems. We also seek possible a

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