New complexity results for the k-covers problem
The k-covers problem (kCP) asks us to compute a minimum cardinality set of stringsof given length k > 1 that covers a given string. It was shown in a recent paper, by reduction to 3-SAT, that the k-covers problem is NP-complete. In this paper we introduce a new problem, that we call the k-Bounded...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
Australian Computer Society
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/45670 |