1.5D terrain guarding problem parameterized by guard range

DOI10.1016/J.TCS.2016.11.015MaRDI QIDQ501659zbMATH OpenOpenAlexFDO

Authors Farnoosh Khodakarami, F. Didehvar, Ali Mohades

Publication date 9 January 2017

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

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

zbMATH Keywords

1.5D terraindynamic programmingguardingparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A fixed-parameter algorithm for guarding 1.5D terrains
• Exact algorithms for terrain guarding
• Exact algorithms for terrain guarding
• The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS
• A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem

Cites work

• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• A fixed-parameter algorithm for guarding 1.5D terrains
• An Approximation Scheme for Terrain Guarding
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• Improved approximations for guarding 1.5-dimensional terrains
• Parameterized algorithms
• Parametrized complexity theory.
• Reflections on multivariate algorithmics and problem parameterization
• Terrain guarding is NP-hard
• Visibility Algorithms in the Plane

Cited in

(10)

• Parameter analysis for guarding terrains
• A fixed-parameter algorithm for guarding 1.5D terrains
• A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem
• Exact algorithms for terrain guarding
• Exact algorithms for terrain guarding
• Parameter analysis for guarding terrains
• One-sided terrain guarding and chordal graphs
• A practical algorithm with performance guarantees for the art gallery problem
• On the discrete and semi-continuous versions of the two-watchtower problem in the plane
• A practical algorithm with performance guarantees for the art gallery problem

This page was built for publication: 1.5D terrain guarding problem parameterized by guard range

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