Back to Search
Start Over
Reversals and Transpositions Over Finite Alphabets.
- Source :
-
SIAM Journal on Discrete Mathematics . 2005, Vol. 19 Issue 1, p224. 21p. - Publication Year :
- 2005
-
Abstract
- Extending results of Christie and Irving, we examine the action of reversals and transpositions on finite strings over an alphabet of size k. We show that determining reversal, transposition, or signed reversal distance between two strings over a finite alphabet is NP-hard, while for "dense" instances we give a polynomial-time approximation scheme. We also give a number of extremal results, as well as investigating the distance between random strings and the problem of sorting a string over a finite alphabet. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MATHEMATICS
*ALPHABET
*APPROXIMATION theory
*POLYNOMIALS
*DISTANCES
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 19
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 18638717
- Full Text :
- https://doi.org/10.1137/S0895480103433550