Necklace swap problem for rhythmic similarity measures

Yoan José Pinzó Ardila, Raphaël Clifford, Costas S. Iliopoulos, Gad M. Landau, Manal Mohamed

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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 possible rotations of B. We show that, given the compressed representation of A and B, this distance may be computed in O(k2).

שפה מקוריתאנגלית אמריקאית
עמודים (מ-עד)351-363
מספר עמודים13
כתב עתInternational Journal of Computational Methods
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2008

הערה ביבליוגרפית

Funding Information:
∗Partially supported by the Israel Science Foundation grant 35/05.

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1701???
  • ???subjectarea.asjc.2600.2605???


להלן מוצגים תחומי המחקר של הפרסום 'Necklace swap problem for rhythmic similarity measures'. יחד הם יוצרים טביעת אצבע מחקרית ייחודית.

פורמט ציטוט ביבליוגרפי