کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
394699 665831 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
New complexity results for the k-covers problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
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-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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 181, Issue 12, 15 June 2011, Pages 2571–2575
نویسندگان
, , ,