Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Reversals And Transpositions Over Finite Alphabets, A. J. Radcliffe, A. D. Scott, E. L. Wilmer
Reversals And Transpositions Over Finite Alphabets, A. J. Radcliffe, A. D. Scott, E. L. Wilmer
Department of Mathematics: Faculty Publications
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.