
doi: 10.1007/11751540_18
In this paper we deal with one of the art gallery problems, namely the problem of fault tolerant guarding of grids, which is defined as the problem of finding two disjoint guard sets in a grid. Although determining the existence of such a structure is easy in general grids, the task of minimising the number of guards taken over both teams is shown to be NP-hard even for subcubic grids. Moreover, we propose a 6/5-approximation algorithm for solving the fault tolerant guard problem in grids.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
