Article ID Journal Published Year Pages File Type
428557 Information Processing Letters 2013 6 Pages PDF
Abstract

The problem of sorting by prefix transpositions asks for the minimum number of prefix transpositions required to sort the elements of a given permutation. In this paper, we study a variant of this problem where the prefix transpositions act not on permutations but on strings over an alphabet of fixed size. Here, we determine the minimum number of prefix transpositions required to sort the binary and ternary strings, with polynomial time algorithms for these sorting problems.

► We study a variant of the problem of sorting by prefix transpositions. ► The transpositions act on strings of fixed size alphabet, rather than permutations. ► We find minimum number prefix transpositions required to sort binary and ternary strings. ► Our method is based on finding a grouping of the alphabets where similar alphabets become consecutive.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,