Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Item 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