کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431115 | 688278 | 2008 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Red-blue covering problems and the consecutive ones property
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Red-blue covering problems and the consecutive ones property Red-blue covering problems and the consecutive ones property](/preview/png/431115.png)
چکیده انگلیسی
Set Cover problems are of core importance in many applications. In recent research, the “red-blue variants” where blue elements all need to be covered whereas red elements add further constraints on the optimality of a covering have received considerable interest. Application scenarios range from data mining to interference reduction in cellular networks. As a rule, these problem variants are computationally at least as hard as the original set cover problem. In this work we investigate whether and how the well-known consecutive ones property, restricting the structure of the input sets, makes the red-blue covering problems feasible. We explore a sharp border between polynomial-time solvability and NP-hardness for these problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 6, Issue 3, September 2008, Pages 393–407
Journal: Journal of Discrete Algorithms - Volume 6, Issue 3, September 2008, Pages 393–407
نویسندگان
Michael Dom, Jiong Guo, Rolf Niedermeier, Sebastian Wernicke,