A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
New lower bound for 2-identifying code in the square grid
Tekijät: Junnila V
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2013
Journal: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: DISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Numero sarjassa: 13-14
Vuosikerta: 161
Numero: 13-14
Aloitussivu: 2042
Lopetussivu: 2051
Sivujen määrä: 10
ISSN: 0166-218X
DOI: https://doi.org/10.1016/j.dam.2013.02.032
Tiivistelmä
An r-identifying code in a graph G = (V, E) is a subset C subset of V such that for each u is an element of V the intersection of C and the ball of radius r centered at u is nonempty and unique. Previously, r-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the square grid with density 5/29 approximate to 0.172 and that there are no 2-identifying codes with density smaller than 3/20 = 0.15. Recently, the lower bound has been improved to 6/37 approximate to 0.162 by Martin and Stanton (2010) [11]. In this paper, we further improve the lower bound by showing that there are no 2-identifying codes in the square grid with density smaller than 6/35 approximate to 0.171. (C) 2013 Elsevier B.V. All rights reserved.
An r-identifying code in a graph G = (V, E) is a subset C subset of V such that for each u is an element of V the intersection of C and the ball of radius r centered at u is nonempty and unique. Previously, r-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the square grid with density 5/29 approximate to 0.172 and that there are no 2-identifying codes with density smaller than 3/20 = 0.15. Recently, the lower bound has been improved to 6/37 approximate to 0.162 by Martin and Stanton (2010) [11]. In this paper, we further improve the lower bound by showing that there are no 2-identifying codes in the square grid with density smaller than 6/35 approximate to 0.171. (C) 2013 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali