Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.3233/978-1-61499-484-8-1960 | Frontiers in Artificial Intelligence and Applications |
Keywords | Field | DocType |
algorithms,block-interchanges,prefix block-interchanges,binary strings | Binary strings,Computer science,Parallel computing,Arithmetic,Prefix,Kraft's inequality,Kibibyte,Prefix code,Trie | Conference |
Volume | ISSN | Citations |
274 | 0922-6389 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shih-Wen Chou | 1 | 0 | 0.34 |
| Chung-Han Yang | 2 | 0 | 0.68 |
| Kun-Tze Chen | 3 | 0 | 1.01 |
| Chin Lung Lu | 4 | 423 | 34.59 |