Discrete Math Seminar Spring 2009
Sorting Signed Permutations with Cut-and-Paste Operations
J. Travis Johnston, UNL;
Mar 24
We consider the problem of determining the maximum number of
cut-and-paste operations required to sort a signed permutations of n
elements to the identity. A cut-and-paste operation is one where a
segment of the permutation is removed (cut) and then replaced into the
remaining permutation (pasted), possibly reversed. This question is
motivated by its applications to evolutionary biology, where the
problem models measuring distance between genomes.