Name
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 (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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1137/060664252 | Information & Computation |
Keywords | DocType | Volume |
prefix reversal,discrete math,ternary string,optimally grouping binary,minimum number,intriguing open problem,minimum prefix reversal distance,polynomial-time algorithm,prefix reversals,prefix reversal diameter,ternary strings,binary string,discrete mathematics | Journal | 21 |
Issue | ISSN | Citations |
3 | 0302-9743 | 5 |
PageRank | References | Authors |
0.57 | 12 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cor Hurkens | 1 | 33 | 3.40 |
| Leo van Iersel | 2 | 215 | 24.58 |
| J. C. M. Keijsper | 3 | 39 | 3.93 |
| Steven Kelk | 4 | 193 | 25.60 |
| Leen Stougie | 5 | 892 | 107.93 |
| John Tromp | 6 | 124 | 12.85 |