Improved parameterized algorithms for minimum link-length rectilinear spanning path problem

The Parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d  -dimensional Euclidean space RdRd (d-RSP), for a given set S of n   points in RdRd 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.74dk)k)O⁎((0.74dk)k).