Computing the minimum k-Cover of a string
Cole, R., Iliopoulos, C.S., Mohamed, M., Smyth, W.F. and Yang, L. (2003) Computing the minimum k-Cover of a string. In: Prague Stringology Conference 2003, 22 - 24 September 2003, Czech Technical University, Prague
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.
|Publication Type:||Conference Paper|
|Item Control Page|
Downloads per month over past year