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

DOI10.1016/J.TCS.2014.07.021MaRDI QIDQ477189zbMATH OpenOpenAlexFDO

Authors Qilong Feng, Chao Xu, Jinyi Yao, Jianxin Wang, Jianer 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)

Recommendations

• Improved FPT Algorithms for Rectilinear k-Links Spanning Path
• Traversing a set of points with a minimum number of turns
• Traversing a set of points with a minimum number of turns
• Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
• Improved lower bounds for the link length of rectilinear spanning paths in grids

Cites work

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

Cited in

(4)

• Improved FPT Algorithms for Rectilinear k-Links Spanning Path
• Improved lower bounds for the link length of rectilinear spanning paths in grids
• Improved kernel results for some FPT problems based on simple observations
• Partition on trees with supply and demand: kernelization and algorithms

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

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