The parameterized complexity of guarding almost convex polygons
From MaRDI portal
\textsc{Art Gallery}fixed parameter tractabilitymonotone 2-CSPparameterized complexityreflex vertices
Numerical solution of boundary value problems involving ordinary differential equations (65L10) Finite difference and finite volume methods for ordinary differential equations (65L12) Stability and convergence of numerical methods for ordinary differential equations (65L20) Error bounds for numerical methods for ordinary differential equations (65L70) Computer science (68-XX)
Recommendations
Cites work
- A combinatorial theorem in plane geometry
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A new upper bound for the VC-dimension of visibility regions
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- A short proof of Chvatal's Watchman Theorem
- Algorithms for polytope covering and approximation
- Almost optimal set covers in finite VC-dimension
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- An approximation algorithm for the art gallery problem
- An exact algorithm for minimizing vertex guards on art galleries
- Approximability of guarding weak visibility polygons
- Approximate guarding of monotone and rectilinear polygons
- Approximation algorithms for art gallery problems in polygons
- Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
- Computational complexity of art gallery problems
- Fast vertex guarding for polygons with and without holes
- Fundamentals of parameterized complexity
- Guarding galleries and terrains
- Guarding galleries where every point sees a large area
- Guarding galleries where no point sees a small area.
- scientific article; zbMATH DE number 4065813 (Why is no real title available?)
- scientific article; zbMATH DE number 1424310 (Why is no real title available?)
- Improved approximation for guarding simple galleries from the perimeter
- Inapproximability results for guarding polygons and terrains
- Irrational guards are sometimes needed
- Mathematical Foundations of Computer Science 2004
- On guarding the vertices of rectilinear domains
- On the combinatorial and algebraic complexity of quantifier elimination
- Parameterized algorithms
- Parameterized hardness of art gallery problems
- Parameterized Hardness of Art Gallery Problems
- Reflections on multivariate algorithmics and problem parameterization
- Some NP-hard polygon decomposition problems
- The art gallery problem is \(\exists \mathbb{R}\)-complete
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- Unsolved problems in visibility graphs of points, segments, and polygons
Cited in
(2)
This page was built for publication: The parameterized complexity of guarding almost convex polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6191439)
