Skip to main content
Top

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.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadata
Title
Improved FPT Algorithms for Rectilinear k-Links Spanning Path
Authors
Jianxin Wang
Jinyi Yao
Qilong Feng
Jianer Chen
Copyright Year
2012
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-29952-0_52

Premium Partner