Back to Search
Start Over
Prefix and suffix reversals on strings.
- Source :
-
Discrete Applied Mathematics . Sep2018, Vol. 246, p140-153. 14p. - Publication Year :
- 2018
-
Abstract
- The Sorting by Prefix Reversals problem consists in sorting the elements of a given permutation π using a minimum number of prefix reversals, i.e. reversals that always involve the leftmost element of π . A natural extension of this problem is to consider strings, in which any letter may appear several times, rather than permutations. In strings, three different types of problems arise: grouping (given a string S , transform it so that all identical letters are consecutive), sorting (a constrained version of grouping, in which the target string must be lexicographically ordered) and rearranging (given two strings S and T , transform S into T ). In this paper, we study these three problems, under an algorithmic viewpoint, in the setting where two operations, rather than one, are allowed: namely, prefix and suffix reversals — where a suffix reversal must always involve the rightmost element of the string. We first compare the “prefix reversals only” case to our case, before presenting a series of algorithmic results on these three problems concerning polynomiality, constant ratio approximation algorithms, NP-hardness and fixed-parameterized tractability. These results depend on the size k of the alphabet on which the strings are built, with a particular focus on small-sized alphabet instances (i.e., k = O ( 1 ) ) and big-sized alphabet instances (i.e. n − k = O ( 1 ) , where n is the length of the input string(s)). [ABSTRACT FROM AUTHOR]
- Subjects :
- *STRING
*PERMUTATIONS
*ALGORITHMS
*PARAMETERS (Statistics)
*MATHEMATICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 246
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 130246239
- Full Text :
- https://doi.org/10.1016/j.dam.2017.07.031