Computing the minimum k-Cover of a string
Richard Cole, Costas S. Iliopoulos, Manal Mohamed, William Franklin Smyth, Lu Yang · Murdoch Research Repository (Murdoch University) · 2003
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 previously proposed on-line algorithm 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.