Improved FPT Algorithms for Rectilinear k-Links Spanning Path

DOI10.1007/978-3-642-29952-0_52MaRDI QIDQ2898068zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Jinyi Yao, Qilong Feng, Jianer Chen

Publication date 16 July 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-29952-0_52

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• Improved lower bounds for the link length of rectilinear spanning paths in grids
• On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms
• An improved FPTAS for Restricted Shortest Path.
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• A linear fixed parameter tractable algorithm for connected pathwidth
• scientific article; zbMATH DE number 7651203

Cited in

(5)

• Is it FPT to cover points with tours on minimum number of bends (errata)?
• FPT-algorithms for minimum-bends tours
• The rectilinear \(k\)-bends TSP
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• On covering points with minimum turns

This page was built for publication: Improved FPT Algorithms for Rectilinear k-Links Spanning Path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2898068)