Name
Abstract | ||
|---|---|---|
A graph G = (V, E) is terrain-like if one can assign a unique integer from the range [1..vertical bar V vertical bar] 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-39479-0_1 | APPROXIMATION AND ONLINE ALGORITHMS (WAOA 2019) |
Field | DocType | Volume |
Graph,Polygon,Combinatorics,Computer science,Terrain | Conference | 11926 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stav Ashur | 1 | 0 | 0.34 |
| Omrit Filtser | 2 | 11 | 6.39 |
| Matthew J. Katz | 3 | 130 | 12.41 |
| Rachel Saban | 4 | 0 | 0.34 |