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

DOI10.1016/j.tcs.2014.07.021zbMath1303.68069OpenAlexW1969393713MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved parameterized algorithms for minimum link-length rectilinear spanning path problem