Guarding polyominoes under k-hop visibility

DOI10.1007/978-3-031-55598-5_19MaRDI QIDQ6547940zbMATH OpenFDO

Authors Omrit Filtser, Erik Krohn, Bengt J. Nilsson, Christian Rieck, Christiane Schmidt

Publication date 31 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-55598-5_19

zbMATH Keywords

\(k\)-hop dominating set\(k\)-hop visibilityapproximationart gallery problempolyominoesVC dimension

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• Computational complexity of the r-visibility guard set problem for polyominoes
• Guarding polyominoes
• Guarding polyominoes, polycubes and polyhypercubes
• Approximability of guarding weak visibility polygons

Cites work

• -nets and simplex range queries
• A linear time algorithm for optimal \(k\)-hop dominating set of a tree
• A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
• A new upper bound for the VC-dimension of visibility regions
• Almost optimal set covers in finite VC-dimension
• Clan embeddings into trees, and low treewidth graphs
• Computational complexity of art gallery problems
• Computational complexity of the r-visibility guard set problem for polyominoes
• Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Guarding galleries where no point sees a small area.
• Guarding polyominoes
• Guarding polyominoes, polycubes and polyhypercubes
• Guarding thin orthogonal polygons is hard
• On r-guarding thin orthogonal polygons
• On orthogonally guarding orthogonal polygons with bounded treewidth
• On pseudo-disk hypergraphs
• Optimal binary space partitions for segments in the plane
• Optimal dynamic program for r-domination problems over tree decompositions
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Relations between packing and covering numbers of a tree
• Some NP-hard polygon decomposition problems
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• The Art Gallery Problem is ∃ℝ-complete
• The VC-Dimension of Visibility on the Boundary of a Simple Polygon

Cited in

(1)

• Guarding polyominoes under k-hop visibility

This page was built for publication: Guarding polyominoes under \(k\)-hop visibility

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