標題: Prefix Block-Interchanges on Binary Strings
作者: Chou, Shih-Wen
Yang, Chung-Han
Chen, Kun-Tze
Lu, Chin Lung
生物資訊及系統生物研究所
Institude of Bioinformatics and Systems Biology
關鍵字: algorithms;block-interchanges;prefix block-interchanges;binary strings
公開日期: 1-Jan-2015
摘要: 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.
URI: http://dx.doi.org/10.3233/978-1-61499-484-8-1960
http://hdl.handle.net/11536/150909
ISSN: 0922-6389
DOI: 10.3233/978-1-61499-484-8-1960
期刊: INTELLIGENT SYSTEMS AND APPLICATIONS (ICS 2014)
Volume: 274
起始頁: 1960
結束頁: 1969
Appears in Collections:Conferences Paper