Improved FPT Algorithms for Rectilinear k-Links Spanning Path Conference Paper uri icon

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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

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

citation count

  • 3

complete list of authors

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

publication date

  • May 2012