On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms
On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms
复制标题
DOI：
10.1109/tc.2013.163
复制
发表时间：
2014-12
影响因子：
3.7
通讯作者：
Jian-xin Wang;Peiqiang Tan;Jinyi Yao;Qilong Feng;Jianer Chen
中科院分区：
文献类型：
--
作者：
Jian-xin Wang;Peiqiang Tan;Jinyi Yao;Qilong Feng;Jianer Chen
在-d维欧几里德空间R （-RSP）中，对于R中给定的一组点和一个正整数，（参数化的）最小链路长度直线生成路径问题是寻找一条至多有k个线段的分段线性路径，该路径覆盖（即包含）in中的所有点，其中in中的所有线段均轴平行。我们首先证明了问题2-RSP是np完全的，改进了之前已知的问题10-RSP是np完全的结果。然后，我们考虑了一个约束的d-RSP问题，其中生成路径中的每个线段必须覆盖给定集合中与之共享同一条直线的所有点。本文提出了一种运行时间为O*((2d)k)的约束-RSP问题的参数化算法，该算法显著改善了之前的最佳结果，并且是第一个运行时间为O*(2O(k))的固定约束-RSP问题的参数化算法。我们证明这些结果可以推广到最小链路长度直线旅行商问题。
The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the -ddimensional Euclidean space R ( -RSP), for a given set of points in R and a positive integer , is to find a piecewise-linear path with at most k line-segments that covers (i.e., contains) all points in , where all line-segments in are axis-parallel. We first prove that the problem 2-RSP is NP-complete, improving the previously known result that the problem 10-RSP is NP-complete. We then consider a constrained d-RSP problem in which each line-segment in the spanning path must cover all the points in the given set that share the same line with . We present a new parameterized algorithm with running time O*((2d )k) for the constrained -RSP problem, which significantly improves the previous best result and is the first parameterized algorithm of running time O*(2O(k)) for the constrained d-RSP problem for a fixed . We show that these results can be extended to the Minimum Link-Length Rectilinear Traveling Salesman problem.