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

abstract

• 2014 Elsevier B.V. The Parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space Rd (d-RSP), for a given set S of n points in ^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.74dk)^k).

authors

• Chen, Jianer

published proceedings

• THEORETICAL COMPUTER SCIENCE

author list (cited authors)

• Feng, Q., Wang, J., Xu, C., Yao, J., & Chen, J.

citation count

• 3

complete list of authors

• Feng, Qilong||Wang, Jianxin||Xu, Chao||Yao, Jinyi||Chen, Jianer

publication date

• December 2014

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

keywords

• Axis-parallel Line
• Line Cover
• Parameterized Algorithm
• Rectilinear Spanning Path

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2014.07.021

start page

• 158

end page

• 171

volume

• 560

issue

• P2

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.tcs.2014.07.021