Parameter analysis for guarding terrains

DOI10.1007/s00453-021-00913-9OpenAlexW4205847196MaRDI QIDQ2118384

Meirav Zehavi, Sudeshna Kolay, Akanksha Agrawal

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00913-9

zbMATH Keywords

terrain guardingkernelizationreflex verticesXP algorithmterrain minima

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (4)

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ One-sided discrete terrain guarding and chordal graphs ⋮ One-sided terrain guarding and chordal graphs ⋮ Clique-width of point configurations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Improved approximations for guarding 1.5-dimensional terrains
• Improved approximation algorithms for geometric set cover
• A fixed-parameter algorithm for guarding 1.5D terrains
• On guarding the vertices of rectilinear domains
• A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
• Guarding terrains via local search
• Terrain Guarding is NP-Hard
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• Exact Algorithms for Terrain Guarding
• Orthogonal Terrain Guarding is NP-complete
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Parameterized Algorithms
• Parameterized Hardness of Art Gallery Problems
• The Parameterized Complexity of Guarding Almost Convex Polygons.

This page was built for publication: Parameter analysis for guarding terrains