کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435542 | 689914 | 2016 | 8 صفحه PDF | دانلود رایگان |
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(n2logn)O(n2logn) 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,logn})O(2kn⋅max{k,logn}) time.
Journal: Theoretical Computer Science - Volume 609, Part 3, 4 January 2016, Pages 561–568