A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Watching Systems in the King Grid
Tekijät: Auger D, Honkala I
Kustantaja: SPRINGER JAPAN KK
Julkaisuvuosi: 2013
Journal: Graphs and Combinatorics
Tietokannassa oleva lehden nimi: GRAPHS AND COMBINATORICS
Lehden akronyymi: GRAPH COMBINATOR
Numero sarjassa: 3
Vuosikerta: 29
Numero: 3
Aloitussivu: 333
Lopetussivu: 347
Sivujen määrä: 15
ISSN: 0911-0119
DOI: https://doi.org/10.1007/s00373-011-1124-0
Tiivistelmä
We consider the infinite King grid where we investigate properties of watching systems, an extension of the notion of identifying code recently introduced by Auger et al. (Discret. Appl. Math., 2011). The latter were extensively studied in the infinite King grid and we compare our results with those holding for (r, a parts per thousand currency signa"")-identifying codes. We prove that for r = 1 and a"" = 1, the minimal density of an identifying code, known to be also holds for watching systems; however, when r is large we give an asymptotic equivalence of the optimal density of watching systems which is much better than identifying codes'. Turning to the case r = 1 and a"" a parts per thousand yen 1, we prove that in a certain sense when a"" a parts per thousand yen 6 the best watching systems in the infinite King grid are trivial, but that this is not the case when a"" a parts per thousand currency sign 4.
We consider the infinite King grid where we investigate properties of watching systems, an extension of the notion of identifying code recently introduced by Auger et al. (Discret. Appl. Math., 2011). The latter were extensively studied in the infinite King grid and we compare our results with those holding for (r, a parts per thousand currency signa"")-identifying codes. We prove that for r = 1 and a"" = 1, the minimal density of an identifying code, known to be also holds for watching systems; however, when r is large we give an asymptotic equivalence of the optimal density of watching systems which is much better than identifying codes'. Turning to the case r = 1 and a"" a parts per thousand yen 1, we prove that in a certain sense when a"" a parts per thousand yen 6 the best watching systems in the infinite King grid are trivial, but that this is not the case when a"" a parts per thousand currency sign 4.
Turun yliopiston Tutkimustietojärjestelmän portaali