One-Sided Discrete Terrain Guarding and Chordal Graphs
| Autor: | Kasthurirangan Prahlad Narasimhan |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Algorithms and Discrete Applied Mathematics ISBN: 9783030678982 CALDAM |
| DOI: | 10.1007/978-3-030-67899-9_10 |
| Popis: | The Terrain Guarding problem, a variant of the famous Art Gallery problem, has garnered significant attention over the last two decades in Computational Geometry from the viewpoint of complexity and approximability. Both the continuous and discrete versions of the problem were shown to be NP-Hard in [14] and to admit a PTAS [8, 15]. The biggest unsolved question regarding this problem is if it is fixed-parameter tractable with respect to the size of the guard set. In this paper, we present two theorems that establish a relationship between a restricted case of the Annotated Terrain Guarding problem and the Clique Cover problem in chordal graphs. These theorems were proved in [11] for a special class of terrains called orthogonal terrains and were used to present a FPT algorithm with respect to the parameter that we require for Discrete Orthogonal Terrain Guarding in [2]. We hope that the results obtained in this paper can, in future work, be used to produce such an algorithm for Discrete Terrain Guarding. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|