A short proof of Chvatal's Watchman Theorem
From MaRDI portal
Publication:1245840
DOI10.1016/0095-8956(78)90059-XzbMath0376.05018WikidataQ55878068 ScholiaQ55878068MaRDI QIDQ1245840
Publication date: 1978
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Related Items
Tight bounds for conflict-free chromatic guarding of orthogonal art galleries, Monitoring maximal outerplanar graphs, Parameterized Analysis of Art Gallery and Terrain Guarding, On gallery watchmen in grids, Bichromatic quadrangulations with Steiner points, Approximate guarding of monotone and rectilinear polygons, An efficient algorithm for guard placement in polygons with holes, Multi-agent deployment for visibility coverage in polygonal environments with holes, Universal Guard Problems, Two-floodlight illumination of convex polygons, Quadrangulations of planar sets, Line segment visibility with sidedness constraints, Guarding polyominoes, polycubes and polyhypercubes, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Smoothing the Gap Between NP and ER, Vertex Guarding for Dynamic Orthogonal Art Galleries, Algorithms for art gallery illumination, Hiding people in polygons, Converting triangulations to quadrangulations, Polychromatic 4-coloring of cubic even embeddings on the projective plane, Generating even triangulations on the Klein bottle, Note on an art gallery problem, Guarding a Polygon Without Losing Touch, Injectively \(k\)-colored rooted forests, The visible-volume function of a set of cameras is continuous, piecewise rational, locally Lipschitz, and semi-algebraic in all dimensions, The dispersive art gallery problem, Polychromatic 4-coloring of cubic bipartite plane graphs, Partial domination of maximal outerplanar graphs, Total domination in maximal outerplanar graphs. II., Guarding Art Galleries: The Extra Cost for Sculptures Is Linear, Improved Bounds for Wireless Localization, Guarding a set of line segments in the plane, Combinatorics and complexity of guarding polygons with edge and point 2-transmitters, The parameterized complexity of guarding almost convex polygons, Topological art in simple galleries, Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces, Art gallery theorems for guarded guards., Extensions of the Art Gallery Theorem, Finding minimum witness sets in orthogonal polygons, On the resolution of the sensitivity conjecture, Simple agents learn to find their way: an introduction on mapping polygons, Multiple point visibility and related problems, Guarding curvilinear art galleries with vertex or point guards, Note on the paper ``K-vertex guarding simple polygons, Total domination in plane triangulations, Distance domination, guarding and covering of maximal outerplanar graphs, Parity-constrained triangulations with Steiner points, Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs, Improved bounds for guarding plane graphs with edges, Guarding polyhedral terrains, The orthogonal art gallery theorem with constrained guards, Traditional Galleries Require Fewer Watchmen, Perfect graphs and guarding rectilinear art galleries, An addition to art galleries with interior walls, Approximation algorithms for art gallery problems in polygons, Improved bounds for wireless localization, Witness (Delaunay) graphs, Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs, A simple proof of the rectilinear art gallery theorem, Orthogonal art galleries with interior walls, Polychromatic 4-coloring of guillotine subdivisions, Facial achromatic number of triangulations on the sphere, LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS, Art galleries with guards of uniform range of vision, Unnamed Item, A Zen master, a Zen monk, a Zen mathematician, New bounds on guarding problems for orthogonal polygons in the plane using vertex guards with halfplane vision, Quadrangulations of a polygon with spirality, Facets for art gallery problems, Domination and outer connected domination in maximal outerplanar graphs, Uniqueness of Self-Similar Solutions to the Network Flow in a Given Topological Class, Exploring and Triangulating a Region by a Swarm of Robots, Optimal art gallery localization is NP-hard, Twenty years of progress of \(\mathrm{JCDCG}^3\), Multiple-guard kernels of simple polygons, Convex dominating sets in maximal outerplanar graphs, Extension to 3-Colorable Triangulations, Isolation number of maximal outerplanar graphs, Semipaired domination in maximal outerplanar graphs, An alternative proof of the rectilinear art gallery theorem, An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries, How to Keep an Eye on Small Things, Improved bounds for guarding plane graphs with edges, Art gallery problem with guards whose range of vision is \(180^{\circ}\), On the number of guard edges of a polygon, Independent domination in outerplanar graphs, On partitioning rectilinear polygons into star-shaped polygons, Triangles and (total) domination in subcubic graphs, How to guard orthogonal polygons: diagonal graphs and vertex covers, Approximability of guarding weak visibility polygons
Cites Work
