New complexity results for the k-covers problem
The k-covers problem (kCP) asks us to compute a minimum cardinality set of strings of 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-bounde...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier Inc
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/14681 |