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: Article in PostScript Article in PDF
 PostScript   PDF