Necklace Swap Problem for Rhythmic Similarity Measures

YJ Pinzón Ardilla; R Clifford; M Mohamed

doi:10.1007/11575832_27

Necklace Swap Problem for Rhythmic Similarity Measures

YJ Pinzón Ardilla, R Clifford, M Mohamed

Algorithms and Complexity

Research output: Contribution to journal › Article (Academic Journal) › peer-review

2 Citations (Scopus)

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(k2).

Translated title of the contribution	Necklace Swap Problem for Rhythmic Similarity Measures
Original language	English
Pages (from-to)	234 - 245
Number of pages	12
Journal	Lecture Notes in Computer Science
DOIs	https://doi.org/10.1007/11575832_27
Publication status	Published - 2005

Bibliographical note

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

Access to Document

10.1007/11575832_27

http://www.springerlink.com/content/u20w368qn37t5182/

Handle.net

Persistent link

Cite this

@article{f48b53c1a62d440cb5acc4f5397a9ae9,

title = "Necklace Swap Problem for Rhythmic Similarity Measures",

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{\textquoteright}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).",

author = "\{Pinz{\'o}n Ardilla\}, YJ and R Clifford and M Mohamed",

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

year = "2005",

doi = "10.1007/11575832\_27",

language = "English",

pages = "234 -- 245",

journal = "Lecture Notes in Computer Science ",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

TY - JOUR

T1 - Necklace Swap Problem for Rhythmic Similarity Measures

AU - Pinzón Ardilla, YJ

AU - Clifford, R

AU - Mohamed, M

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

PY - 2005

Y1 - 2005

N2 - 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).

AB - 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).

U2 - 10.1007/11575832_27

DO - 10.1007/11575832_27

M3 - Article (Academic Journal)

SN - 0302-9743

SP - 234

EP - 245

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

ER -

Necklace Swap Problem for Rhythmic Similarity Measures

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this