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

[img]
Preview

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.

Publication Type: Conference Paper
Conference Website: http://www.stringology.org/event/2003/
URI: http://researchrepository.murdoch.edu.au/id/eprint/27807
Item Control Page Item Control Page

Downloads

Downloads per month over past year