Cooperative mobile guards in grids

DOI10.1016/j.comgeo.2006.11.002zbMath1121.65021OpenAlexW2095509593MaRDI QIDQ876501

Paweł Żyliński, Michał Małafiejski, Adrian Kosowski

Publication date: 18 April 2007

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2006.11.002

zbMATH Keywords

mobile guardscooperative guardsquadratic time algorithmsimple grids

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Global defensive sets in graphs, A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras, Mobile versus point guards, Watchman routes for lines and line segments, Packing \([1, \Delta \)-factors in graphs of small degree], THE MINIMUM GUARDING TREE PROBLEM, Algorithms and Complexity of Alliances in Graphs, The searchlight problem for road networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orthogonal segment stabbing
• Galleries need fewer mobile guards: A variation on Chvatal's theorem
• On gallery watchmen in grids
• A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments
• An optimal algorithm to solve the minimum weakly cooperative guards problem for 1-spiral polygons
• A combinatorial theorem in plane geometry
• Art gallery theorems for guarded guards.
• Covering grids and orthogonal polygons with periscope guards
• Watched guards in art galleries
• Steiner trees, connected domination and strongly chordal graphs
• Planar 3DM is NP-complete
• An Efficient Algorithm for Mobile Guarded Guards in Simple Grids