An exact algorithm for minimizing vertex guards on art galleries

DOI10.1111/j.1475-3995.2011.00804.xzbMath1269.90151DBLPjournals/itor/CoutoRS11OpenAlexW2050734728WikidataQ56504464 ScholiaQ56504464MaRDI QIDQ4910663

Pedro J. de Rezende, Marcelo C. Couto, Cid Carvalho De Souza

Publication date: 19 March 2013

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/j.1475-3995.2011.00804.x

zbMATH Keywords

set coveringvisibilityart gallery problemexact algorithm

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (9)

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Universal Guard Problems ⋮ Algorithms for art gallery illumination ⋮ Constrained Light Deployment for Reducing Energy Consumption in Buildings ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Algorithm 966 ⋮ Facets for art gallery problems ⋮ Solving the natural wireless localization problem to optimality efficiently ⋮ How to guard orthogonal polygons: diagonal graphs and vertex covers

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for art gallery problems in polygons
• Corrections to Lee's visibility polygon algorithm
• A combinatorial theorem in plane geometry
• Approximation algorithms for terrain guarding.
• Efficient visibility queries in simple polygons
• Visibility of a simple polygon
• Traditional Galleries Require Fewer Watchmen
• Computational complexity of art gallery problems
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• Visibility Algorithms in the Plane

This page was built for publication: An exact algorithm for minimizing vertex guards on art galleries