کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871866 | 681668 | 2016 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
ترجمه فارسی عنوان
مجموعه ای از ستارگان هندسی، مجموعه پوشش و مشکلات پوشش کلی طبقه بندی شده با نیمه نوار در جهت مخالف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that hitting set and set cover problems with half-strips oriented in two opposite directions are NP-complete. Further, we prove that two variations of the generalized class cover problem on half-strips oriented in two opposite directions are NP-complete, thus resolving two open problems we posed in Mudgal and Pandit (2014) [12].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 143-162
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 143-162
نویسندگان
Apurva Mudgal, Supantha Pandit,