DIMACS TR: 95-18

Sorting with Fixed-Length Reversals



Authors: Ting Chen, Steven S. Skiena

ABSTRACT

We investigate the problem of sorting circular permutations of length $n$ using reversals of length $k$. Of interest is the connectivity and diameter of the underlying group. For all values of $n$ and $k$, we characterize the number of connected components of the underlying group. To bound the diameter of the group, we give an algorithm to sort all sortable circular permutations in $0(n^{2}/k+nk)$ reversals, and show that $\Omega(n^{2}/k^{2}+n)$ reversals are necessary.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-18.ps.gz
DIMACS Home Page