The set of parameterized k-covers problem

• DOI: 10.1016/j.tcs.2011.12.052
• Publication Date: 2011-12-23T16:55:33Z
• Authors: A.A. Gorbenko; V.Yu. Popov
• Keywords: NP-COMPLETE; PARAMETERIZED PATTERN MATCHING; LOGICAL MODELS; 0103 physical sciences; SET OF K-COVERS; Set of k-covers; Parameterized pattern matching; Logical models; 01 natural sciences; NP-complete

AbstractThe problem of the set of k-covers is a distance measure for strings. Another well-studied string comparison measure is that of parameterized matching. We consider the problem of the set of parameterized k-covers (k-SPC) which combines k-cover measure with parameterized matching. We prove that k-SPC is NP-complete. We describe an approach to solve k-SPC. This approach is based on constructing a logical model for k-SPC.