### 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 |

### Bibliographical note

Conference Proceedings/Title of Journal: Proceedings of the 12th International Symposium on String Processing and Information Retrieval (SPIRE '05)## Fingerprint Dive into the research topics of 'Necklace Swap Problem for Rhythmic Similarity Measures'. Together they form a unique fingerprint.

## Cite this

Clifford, R., Mohamed, M., & Pinzon, Y. (2005). Necklace Swap Problem for Rhythmic Similarity Measures. In

*Unknown*(pp. 234 - 245). Springer Verlag. http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000454