A fixed-parameter algorithm for guarding 1.5D terrains

DOI10.1016/j.tcs.2015.06.028zbMath1328.68262OpenAlexW2191206483MaRDI QIDQ2354771

Farzad Didehvar, Ali Mohades, Farnoosh Khodakarami

Publication date: 24 July 2015

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

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

zbMATH Keywords

tree decompositionguardingfixed-parameter algorithm1.5D terrainonion peeling

Mathematics Subject Classification ID

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

Related Items (6)

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ One-sided discrete terrain guarding and chordal graphs ⋮ One-sided terrain guarding and chordal graphs ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ Altitude terrain guarding and guarding uni-monotone polygons ⋮ Parameter analysis for guarding terrains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximations for guarding 1.5-dimensional terrains
• Improved approximation algorithms for geometric set cover
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Parametrized complexity theory.
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Terrain Guarding is NP-Hard
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• An Approximation Scheme for Terrain Guarding
• On the convex layers of a planar set
• Graph minors. II. Algorithmic aspects of tree-width
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Visibility Algorithms in the Plane

This page was built for publication: A fixed-parameter algorithm for guarding 1.5D terrains