Conference paper
On-line algorithms for k-Covering
9th Australasian Workshop on Combinatorial Algorithms (AWOCA '98) (Perth, Western Australia, 27/07/1998–30/07/1998)
1998
Abstract
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.
Details
- Title
- On-line algorithms for k-Covering
- Authors/Creators
- C.S. Iliopoulos (Author/Creator)W.F. Smyth (Author/Creator)
- Conference
- 9th Australasian Workshop on Combinatorial Algorithms (AWOCA '98) (Perth, Western Australia, 27/07/1998–30/07/1998)
- Identifiers
- 991005544399207891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference paper
Metrics
105 File views/ downloads
36 Record Views