New complexity results for the k-covers problem
MetadataShow full item record
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 Relaxed Vertex Cover Problem (RVCPk), which we show is equivalent to k-Bounded Set Cover (SCPk). We show further that kCP is a special case of RVCPk restricted to certain classes Gx,k of graphs that represent all strings x. Thus a minimum k-cover can be approximated to within a factor k in polynomial time. We discuss approximate solutions of kCP, and we state a number of conjectures and open problems related to kCP and Gx,k.
Showing items related by title, author, creator and subject.
Iliopoulos, Costas; Mohamed, M.; Smyth, William (2011)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 ...
Aizam, Nur Aidya Hanum (2013)Timetabling is a table of information showing when certain events are scheduled to take place. Timetabling is in fact very essential in making sure that all events occur in the time and place required. It is critical in ...
Kusumah, Yaya S, (2001)The facility layout design problem is concerned with determining the arrangement and configuration of facilities, which optimizes a prescribed objective such as profit, cost, or distance, and which satisfies various ...