The Prague Stringology Conference 2003
Richard Cole, Costas S. Iliopoulos, Manal Mohamed, William F. Smyth and Lu Yang
Computing the Minimum k-Cover of a String
| Abstract: |
| We study the minimum k-cover problem. For a given string x of length n and an integer k, the minimum k-cover is the minimum set of k-substrings that covers x. We show that the on-line algorithm that has been proposed by Iliopoulos and Smyth [IS92] is not correct. We prove that the problem is in fact NP-hard. Furthermore, we propose two greedy algorithms that are implemented and tested on different kind of data. |
| Download paper: |  |
 |
| PostScript |