A1 Refereed original research article in a scientific journal
On identifying codes in the triangular and square grids
Authors: Honkala I, Laihonen T
Publisher: SIAM PUBLICATIONS
Publication year: 2004
Journal: SIAM Journal on Computing
Journal name in source: SIAM JOURNAL ON COMPUTING
Journal acronym: SIAM J COMPUT
Volume: 33
Issue: 2
First page : 304
Last page: 312
Number of pages: 9
ISSN: 0097-5397
DOI: https://doi.org/10.1137/S0097539703433110(external)
Abstract
It is shown that in the infinite square grid the density of every (r,less than or equal to 2)-identifying code is at least 1/8 and that there exists a sequence C-r of (r, less than or equal to 2)-identifying codes such that the density of C-r tends to 1/8 when r --> infinity. In the infinite triangular grid a sequence C'(r) of (r, less than or equal to 2)-identifying codes is given such that the density of C'(r) tends to 0 when r --> infinity.
It is shown that in the infinite square grid the density of every (r,less than or equal to 2)-identifying code is at least 1/8 and that there exists a sequence C-r of (r, less than or equal to 2)-identifying codes such that the density of C-r tends to 1/8 when r --> infinity. In the infinite triangular grid a sequence C'(r) of (r, less than or equal to 2)-identifying codes is given such that the density of C'(r) tends to 0 when r --> infinity.
UTU Research Portal