Catalog Home Page

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