## 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 to B, minimized
over all rotations of B. We show that this distance may be
computed in O(k^2).

Translated title of the contribution | Necklace Swap Problem for Rhythmic Similarity Measures |
---|---|

Original language | English |

Title of host publication | Unknown |

Publisher | Springer Verlag |

Pages | 234 - 245 |

Number of pages | 11 |

ISBN (Print) | 3540297405 |

Publication status | Published - Nov 2005 |