Browsing by Author "Chou, Shih-Wen"

Now showing 1 - 1 of 1

Prefix Block-Interchanges on Binary Strings
(2015-01-01)
Chou, Shih-Wen
;
Yang, Chung-Han
;
Chen, Kun-Tze
;
Lu, Chin Lung
;
生物資訊及系統生物研究所
A block-interchange acting on a string s exchanges two non-overlapping but not necessary adjacent substrings in s. A prefix block-interchange is a special block-interchange in which one of the two exchanged substrings is restricted to a prefix of s. In this study, we study the problem of sorting by prefix block-interchanges on binary strings, which is to find the minimum number of prefix block-interchanges to sort a given binary string. In addition, we study the problem of computing the prefix block-interchange distance between two binary strings, which is to compute the minimum number of prefix block-interchanges to transform a given binary string into another given binary string. Consequently, we design a linear-time algorithm to solve the problem of sorting by prefix block-interchange on binary strings and also show that the problem of computing the prefix block-interchange distance between two binary strings is NP-hard.