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