Necklace Swap Problem for Rhythmic Similarity Measures

YJ Pinzón Ardilla, R Clifford, M Mohamed

Research output: Contribution to journalArticle (Academic Journal)peer-review

2 Citations (Scopus)


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(k2).
Translated title of the contributionNecklace Swap Problem for Rhythmic Similarity Measures
Original languageEnglish
Pages (from-to)234 - 245
Number of pages12
JournalLecture Notes in Computer Science
Publication statusPublished - 2005

Bibliographical note

ISBN: 9783540297406
Publisher: Springer
Name and Venue of Conference: 12th International Conference, SPIRE 2005, Buenos Aires, Argentina, November 2-4, 2005


Dive into the research topics of 'Necklace Swap Problem for Rhythmic Similarity Measures'. Together they form a unique fingerprint.

Cite this