کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435542 689914 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Shortest color-spanning intervals
ترجمه فارسی عنوان
کوتاه ترین فواصل زمان بندی رنگ
کلمات کلیدی
اشیای رنگ آمیزی هندسه محاسباتی، الگوریتم های دقیق پیچیدگی پارامتریک
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Given a set of n points on a line, where each point has one of k   colors, and given an integer si≥1si≥1 for each color i  , 1≤i≤k1≤i≤k, the problem Shortest Color-SpanningtIntervals (SCSI-t) aims at finding t   intervals to cover at least sisi points of each color i  , such that the maximum length of the intervals is minimized. Chen and Misiolek introduced the problem SCSI-1, and presented an algorithm running in O(n)O(n) time if the input points are sorted. Khanteimouri et al. gave an O(n2log⁡n)O(n2log⁡n) time algorithm for the special case of SCSI-2 with si=1si=1 for all colors i  . In this paper, we present an improved algorithm with running time of O(n2)O(n2) for SCSI-2 with arbitrary si≥1si≥1. We also obtain some interesting results for the general problem SCSI-t. From the negative direction, we show that approximating SCSI-t within any ratio is NP-hard when t is part of the input, is W[2]-hard when t is the parameter, and is W[1]-hard with both t and k as parameters. Moreover, the NP-hardness and the W[2]-hardness with parameter t   hold even if si=1si=1 for all i. From the positive direction, we show that SCSI-t   with si=1si=1 for all i is fixed-parameter tractable with k   as the parameter, and admits an exact algorithm running in O(2kn⋅max⁡{k,log⁡n})O(2kn⋅max⁡{k,log⁡n}) time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 609, Part 3, 4 January 2016, Pages 561–568
نویسندگان
, ,