کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225739 | 1701208 | 2019 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
NP-hardness of geometric set cover and hitting set with rectangles containing a common point
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We prove that both set cover and hitting set problems with points and axis-parallel rectangles are NP-hard even when (i) all rectangles share a common point and (ii) there are only two types of rectangles aÃb and bÃa for some positive integers a and b.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 141, January 2019, Pages 1-8
Journal: Information Processing Letters - Volume 141, January 2019, Pages 1-8
نویسندگان
Raghunath Reddy Madireddy, Apurva Mudgal,