Necklace Swap Problem for  Rhythmic Similarity Measures

R Clifford; M Mohamed; Y Pinzon

Necklace Swap Problem for Rhythmic Similarity Measures

R Clifford, M Mohamed, Y Pinzon

Algorithms and Complexity

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

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)

Access to Document

http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000454

Handle.net

Persistent link

Cite this

@inproceedings{81e3d7bd6d944f8394711a952e4a38d4,

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'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\textasciicircum{}2). ",

author = "R Clifford and M Mohamed and Y Pinzon",

note = "Conference Proceedings/Title of Journal: Proceedings of the 12th International Symposium on String Processing and Information Retrieval (SPIRE '05)",

year = "2005",

month = nov,

language = "English",

isbn = "3540297405",

pages = "234 -- 245",

booktitle = "Unknown",

publisher = "Springer Verlag",

address = "Germany",

}

TY - GEN

T1 - Necklace Swap Problem for Rhythmic Similarity Measures

AU - Clifford, R

AU - Mohamed, M

AU - Pinzon, Y

N1 - Conference Proceedings/Title of Journal: Proceedings of the 12th International Symposium on String Processing and Information Retrieval (SPIRE '05)

PY - 2005/11

Y1 - 2005/11

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(k^2).

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(k^2).

M3 - Conference Contribution (Conference Proceeding)

SN - 3540297405

SP - 234

EP - 245

BT - Unknown

PB - Springer Verlag