کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950931 | 1441044 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Refined algorithms for hitting many intervals
ترجمه فارسی عنوان
الگوریتم های تصفیه شده برای ضربه زدن به بسیاری از فواصل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تجزیه و تحلیل الگوریتم ها، برنامه ریزی با شکاف، قرار دادن مجموعه، نمودار فاصله، برنامه نویسی دینامیک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Within a study of scheduling problems with gaps, Chrobak et al. (CIAC 2015) have shown how to find γ points on the line that hit a maximum number of intervals, in a given family of n intervals, in O(γn2) time. The problem is equivalent to finding γ cliques in an interval graph that cover a maximum number of distinct vertices. We give refined algorithms that run faster if the interval graph of the family is sparse.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 118, February 2017, Pages 117-122
Journal: Information Processing Letters - Volume 118, February 2017, Pages 117-122
نویسندگان
Peter Damaschke,