Computing the minimum k-Cover of a string

R. Cole; C.S. Iliopoulos; M. Mohamed; W.F. Smyth; L. Yang

Back

Computing the minimum k-Cover of a string

Conference paper

Open access

Computing the minimum k-Cover of a string

R. Cole, C.S. Iliopoulos, M. Mohamed, W.F. Smyth and L. Yang

Prague Stringology Conference 2003 (Czech Technical University, Prague, 22/09/2003–24/09/2003)

2003

Files and links (2)

pdf

computing_the_minimum.pdfDownload View

Open Access

url

Conference WebsiteView

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.

Details

Title: Computing the minimum k-Cover of a string
Authors/Creators: R. Cole (Author/Creator)
C.S. Iliopoulos (Author/Creator)
M. Mohamed (Author/Creator)
W.F. Smyth (Author/Creator)
L. Yang (Author/Creator)
Conference: Prague Stringology Conference 2003 (Czech Technical University, Prague, 22/09/2003–24/09/2003)
Identifiers: 991005540067207891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Conference paper

Metrics

107 File views/ downloads

49 Record Views