Improved FPT Algorithms for Rectilinear k-Links Spanning Path
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Given n points in d and a positive integer k, the Rectilinear k-Links Spanning Path problem is to find a piecewise linear path through these n points having at most k line-segments (Links) where these line-segments are axis-parallel. This problem is known to be NP-complete when d 3, we first prove that it is also NP-complete in 2-dimensions. Under the assumption that one line-segment in the spanning path covers all the points on the same line, we propose a new FPT algorithm with running time O(d k+12 kk 2+d kn), which greatly improves the previous best result and is the first FPT algorithm that runs in O*(2 O(k)). When d = 2, we further improve this result to O(3.24 kk 2 + 1.62 kn). For the Rectilinear k-Bends TSP problem, the NP-completeness proof in 2-dimensions and FPT algorithms are also given. 2012 Springer-Verlag.
name of conference
Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings