Mathematics – Geometric Topology
Scientific paper
2007-02-13
Mathematics
Geometric Topology
31 pages; This preprint is published in no journal, and divided into separate papers with more contents.
Scientific paper
Recently, there have been several progresses for the conjugacy search problem (CSP) in Garside groups, especially in braid groups. All known algorithms for solving this problem use a sort of exhaustive search in a particular finite set such as the super summit set and the ultra summit set. Their complexities are proportional to the size of the finite set, even when there exist very short conjugating elements. However, ultra summit sets are very large in some cases especially for reducible braids and periodic braids. Some possible approaches to resolve this difficulty would be either to use different Garside structures and Garside groups in order to get a sufficiently small ultra summit set, or to develop an algorithm for finding a conjugating element faster than exhaustive search. Using the former method, Birman, Gonz\'alez-Meneses and Gebhardt have proposed a polynomial-time algorithm for the CSP for periodic braids. In this paper we study the conjugacy classes of periodic braids under the BKL Garside structure, and show that we can solve the CSP for periodic braids in polynomial time although their ultra summit sets are exponentially large. Our algorithm describes how to connect two periodic braids in the (possibly exponentially large) ultra summit set by applying partial cycling polynomially many times.
Lee Eon-Kyung
Lee Sang Jin
No associations
LandOfFree
Conjugacy classes of periodic braids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Conjugacy classes of periodic braids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conjugacy classes of periodic braids will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-409710