TCS Journal 2014 Journal Article
Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
- Qilong Feng
- Jianxin Wang
- Chao Xu
- Jinyi Yao
- Jianer Chen
The Parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R d (d-RSP), for a given set S of n points in R d and a positive integer k, is to find a rectilinear spanning path P with at most k line-segments that cover all points in S, where all line-segments in P are axis-parallel. In this paper, we study a constrained d-RSP problem (Constrained d-RSP problem) in which each line-segment l in the spanning path must cover all the points in S that share the same line with l. By applying the branch-and-search and dynamic programming techniques, a parameterized algorithm with running time O ⁎ ( ( 1 + 1 + 4 ( d − 1 ) 2 ) k ) is given for the Constrained d-RSP problem, which significantly improves the current best result O ⁎ ( ( 0. 74 d k ) k ).