Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains
verfasst von : Stav Ashur, Omrit Filtser, Matthew J. Katz, Rachel Saban
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A graph \(G = (V,E)\) is terrain-like if one can assign a unique integer from the range [1..|V|] to each vertex in V, such that, if both \(\{i,k\}\) and \(\{j,l\}\) are in E, for any \(i< j< k < l\), then so is \(\{i,l\}\). We present a local-search-based PTAS for minimum dominating set in terrain-like graphs. Then, we observe that, besides the visibility graphs of x-monotone terrains which are terrain-like, so are the visibility graphs of weakly-visible polygons and weakly-visible terrains, immediately implying a PTAS for guarding the vertices of such a polygon or terrain from its vertices. We also present PTASs for continuously guarding the boundary of a WV-polygon or WV-terrain, either from its vertices, or, for a WV-terrain, from arbitrary points on the terrain. Finally, we compare between terrain-like graphs and non-jumping graphs, and also observe that both families admit PTASs for maximum independent set.