Sorting by Reversals Demo
- The goal is to sort a permutation array to the identity permutation only by reversing subarrays of it in the minimal number of reversals.
- Choose the size of an array, enter it in the box at the lower left corner,
then click on [GO]. A random array of the chosen size will be displayed.
- Click on two of the boxes of the array. The subarray between and
including them will be reversed.
- Indicates the number of reversals.
P. Berman, S. Hannenhalli, and M. Karpinski,
1.375-Approximation Algorithm for Sorting by Reversals,
Proc. 10th ESA (2002), LNCS Vol. 2461, pp. 200-210, 2002.
P. Berman and M. Karpinski,
On Some Tighter Inapproximability Results,
Proc. 26th ICALP (1999), LNCS Vol. 1644, pp. 200-209, 1999.
V. Bafna and P.A. Pevzner,