תקציר
A graph = (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 and are in E, for any, then so is 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.
| שפה מקורית | אנגלית |
|---|---|
| כותר פרסום המארח | Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Revised Selected Papers |
| עורכים | Evripidis Bampis, Nicole Megow |
| מוציא לאור | Springer |
| עמודים | 1-17 |
| מספר עמודים | 17 |
| מסת"ב (מודפס) | 9783030394783 |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - 2019 |
| פורסם באופן חיצוני | כן |
| אירוע | 17th International Workshop on Approximation and Online Algorithms, WAOA 2019 - Munich, גרמניה משך הזמן: 12 ספט׳ 2019 → 13 ספט׳ 2019 |
סדרות פרסומים
| שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| כרך | 11926 LNCS |
| ISSN (מודפס) | 0302-9743 |
| ISSN (אלקטרוני) | 1611-3349 |
כנס
| כנס | 17th International Workshop on Approximation and Online Algorithms, WAOA 2019 |
|---|---|
| מדינה/אזור | גרמניה |
| עיר | Munich |
| תקופה | 12/09/19 → 13/09/19 |
הערה ביבליוגרפית
Publisher Copyright:© 2020, Springer Nature Switzerland AG.