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

DOI10.1016/J.TCS.2014.07.021zbMATH Open1303.68069OpenAlexW1969393713MaRDI QIDQ477189FDOQ477189

Chao Xu, Qilong Feng, 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

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

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)

Cites Work

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

Cited In (4)

• Improved FPT Algorithms for Rectilinear k-Links Spanning Path
• An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains
• 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)