Prefix reversals on binary and ternary strings

C.A.J. Hurkens, L.J.J. Iersel, van, J.C.M. Keijsper, S.M. Kelk, L. Stougie, J.T. Tromp

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
107 Downloads (Pure)

Abstract

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 (Discrete Math., 27 (1979), 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.
Original languageEnglish
Pages (from-to)592-611
JournalSIAM Journal on Discrete Mathematics
Volume21
Issue number3
DOIs
Publication statusPublished - 2007

Fingerprint

Dive into the research topics of 'Prefix reversals on binary and ternary strings'. Together they form a unique fingerprint.

Cite this