2012 | OriginalPaper | Chapter
Improved FPT Algorithms for Rectilinear k-Links Spanning Path
Authors : Jianxin Wang, Jinyi Yao, Qilong Feng, Jianer Chen
Published in: Theory and Applications of Models of Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
+ 1
2
k
k
2
+
d
k
n
), 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
k
k
2
+ 1.62
k
n
). For the Rectilinear
k
-Bends TSP problem, the NP-completeness proof in 2-dimensions and FPT algorithms are also given.