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

On-line algorithms for k-Covering

Iliopoulos, C.S. and Smyth, W.F. (1998) On-line algorithms for k-Covering. In: 9th Australasian Workshop on Combinatorial Algorithms (AWOCA '98), 27 - 30 July 1998, Perth, Western Australia



An O(n2(n-k)) on-line algorithm for computing a minimum set of k-covers for a given string of length n is presented. A straightforward modification of the algorithms yields O(kn2(n-k)) algorithms for computing a minimum set of k-covers and k-segments for a given circular string of length n. We show further that the number of such minimum sets of k-covers may be exponential. Similar time complexity bounds hold for computing the minimum sets of k-segments and k-seeds.

Item Type: Conference Paper
Item Control Page Item Control Page


Downloads per month over past year