Shortest color-spanning intervals

详细信息    查看全文

• 作者：Minghui Jiang ; ^{mjiang@cc.usu.edu" class="auth_mail" title="E-mail the corresponding author} ; Haitao Wang¹ ; ^{haitao.wang@usu.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Color-spanning objects ; Computational geometry ; Exact algorithms ; Parameterized complexity
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 January 2016
• 年：2016
• 卷：609
• 期：part_P3
• 页码：561-568
• 全文大小：330 K

文摘

Given a set of n points on a line, where each point has one of k   colors, and given an integer s_i≥1$s_i\ge 1$ for each color i  , 1≤i≤k$1\le i\le k$, the problem Shortest Color-SpanningtIntervals (SCSI-t) aims at finding t   intervals to cover at least s_i$s_i$ 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(n²log⁡n)$O(n^2\log n)$ time algorithm for the special case of SCSI-2 with s_i=1$s_i=1$ for all colors i  . In this paper, we present an improved algorithm with running time of O(n²)$O(n^2)$ for SCSI-2 with arbitrary s_i≥1$s_i\ge 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 s_i=1$s_i=1$ for all i. From the positive direction, we show that SCSI-t   with s_i=1$s_i=1$ for all i is fixed-parameter tractable with k   as the parameter, and admits an exact algorithm running in O(2^kn⋅max⁡{k,log⁡n})$O(2^{k}n\cdot \max \{k,\log n\})$ time.