Improved parameterized algorithms for minimum link-length rectilinear spanning path problem

DOI10.1016/j.tcs.2014.07.021zbMath1303.68069MaRDI QIDQ477189

Chao Xu, Qilong Feng, Jinyi Yao, Jianxin Wang, Jian'er Chen

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.021

zbMATH Keywords

parameterized algorithmaxis-parallel lineline coverrectilinear spanning path

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

90C39: Dynamic programming

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Partition on trees with supply and demand: kernelization and algorithms, Improved kernel results for some FPT problems based on simple observations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
• Parameterized complexity of max-lifetime target coverage in wireless sensor networks
• A parameterized algorithm for the hyperplane-cover problem
• Minimum-link watchman tours
• Approximation algorithms for hitting objects with straight lines
• Rectilinear paths among rectilinear obstacles
• Improved FPT Algorithms for Rectilinear k-Links Spanning Path
• Covering a Set of Points with a Minimum Number of Lines
• SHORTEST PATH QUERIES IN RECTILINEAR WORLDS
• COVERING A SET OF POINTS WITH A MINIMUM NUMBER OF TURNS
• On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms
• Optimal Covering Tours with Turn Costs
• The Traveling-Salesman Problem and Minimum Spanning Trees
• On Covering Points with Minimum Turns
• Traversing a set of points with a minimum number of turns