The parameterized complexity of guarding almost convex polygons
DOI10.1007/s00454-023-00569-yOpenAlexW3012424674MaRDI QIDQ6191439
Akanksha Agrawal, Kristine V. K. Knudsen, Saket Saurabh, Daniel Lokshtanov, Meirav Zehavi
Publication date: 9 February 2024
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-023-00569-y
fixed parameter tractabilityparameterized complexityreflex verticesmonotone 2-CSP\textsc{Art Gallery}
Stability and convergence of numerical methods for ordinary differential equations (65L20) Numerical solution of boundary value problems involving ordinary differential equations (65L10) Error bounds for numerical methods for ordinary differential equations (65L70) Finite difference and finite volume methods for ordinary differential equations (65L12) Computer science (68-XX)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- A new upper bound for the VC-dimension of visibility regions
- Improved approximation for guarding simple galleries from the perimeter
- Guarding galleries and terrains
- Approximation algorithms for art gallery problems in polygons
- A short proof of Chvatal's Watchman Theorem
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Guarding galleries where no point sees a small area.
- Guarding galleries where every point sees a large area
- A combinatorial theorem in plane geometry
- Almost optimal set covers in finite VC-dimension
- Fast vertex guarding for polygons with and without holes
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- Approximability of guarding weak visibility polygons
- Approximate guarding of monotone and rectilinear polygons
- On guarding the vertices of rectilinear domains
- Reflections on Multivariate Algorithmics and Problem Parameterization
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Computational complexity of art gallery problems
- Some NP-hard polygon decomposition problems
- On the combinatorial and algebraic complexity of quantifier elimination
- Irrational Guards are Sometimes Needed
- Parameterized Hardness of Art Gallery Problems
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- An exact algorithm for minimizing vertex guards on art galleries
- Algorithms for polytope covering and approximation
- The art gallery problem is ∃ ℝ-complete
- Mathematical Foundations of Computer Science 2004
- Unsolved problems in visibility graphs of points, segments, and polygons
- Parameterized Algorithms
- Parameterized Hardness of Art Gallery Problems
- Inapproximability results for guarding polygons and terrains
This page was built for publication: The parameterized complexity of guarding almost convex polygons
