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