Prefix reversals on binary and ternary strings

Details Prefix reversals on binary and ternary strings Prefix reversals on binary and ternary strings

2006-02-21

arxiv.org/abs/math/0602456v2

Mathematics

Combinatorics

20 pages. Just submitted for journal publication. Previous version should be considered no longer valid

Scientific paper

Given a permutation pi, the application of prefix reversal f^(i) to pi reverses the order of the first i elements of pi. The problem of Sorting By Prefix Reversals (also known as pancake flipping), made famous by Gates and Papadimitriou (Bounds for sorting by prefix reversal, Discrete Mathematics 27, pp. 47-57), asks for the minimum number of prefix reversals required to sort the elements of a given permutation. In this paper we study a variant of this problem where the prefix reversals act not on permutations but on strings over a fixed size alphabet. We determine the minimum number of prefix reversals required to sort binary and ternary strings, with polynomial-time algorithms for these sorting problems as a result; demonstrate that computing the minimum prefix reversal distance between two binary strings is NP-hard; give an exact expression for the prefix reversal diameter of binary strings, and give bounds on the prefix reversal diameter of ternary strings. We also consider a weaker form of sorting called grouping (of identical symbols) and give polynomial-time algorithms for optimally grouping binary and ternary strings. A number of intriguing open problems are also discussed.

Affiliated with

Also associated with

No associations

Rating

Prefix reversals on binary and ternary strings 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 Prefix reversals on binary and ternary strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefix reversals on binary and ternary strings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-454455