The Prague Stringology Conference 2005
Yoan Pinzón, Costas S. Iliopoulos, Gad M. Landau and Manal Mohamed
Approximation Algorithm for the Cyclic Swap Problem
| Abstract: |
| Given two n-bit (cyclic) binary strings, A and B, represented on a circle (necklace instances). Let each sequence have the same number k of 1's. We are interested in computing the cyclic swap distance between A and B, i.e., the minimum number of swaps needed to convert A into B, minimized over all rotations of B. We show that this distance may be approximated in O(n+k2) time. |
| Download paper: |  |
 |
| PostScript |