Catalog Home Page

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.

Item Type: Conference Paper
Conference Website:
Item Control Page Item Control Page


Downloads per month over past year