A1 Refereed original research article in a scientific journal
On codes identifying vertices in the two-dimensional square lattice with diagonals
Authors: Cohen GD, Honkala I, Lobstein A, Zemor G
Publisher: IEEE COMPUTER SOC
Publication year: 2001
Journal: IEEE Transactions on Computers
Journal name in source: IEEE TRANSACTIONS ON COMPUTERS
Journal acronym: IEEE T COMPUT
Volume: 50
Issue: 2
First page : 174
Last page: 176
Number of pages: 3
ISSN: 0018-9340
DOI: https://doi.org/10.1109/12.908992
Abstract
Fault diagnosis of multiprocessor systems motivates the following graph-theoretic definition. A subset C of points in an undirected graph G = (V, E) is called an identifying code if the sets B(upsilon) boolean AND C consisting of all elements of C within distance one from the vertex upsilon are different. We also require that the sets B(upsilon) boolean AND C are all nonempty. We take G to be the infinite square lattice with diagonals and show that the density of the smallest identifying code is at least 2/9 and at most 4/17.
Fault diagnosis of multiprocessor systems motivates the following graph-theoretic definition. A subset C of points in an undirected graph G = (V, E) is called an identifying code if the sets B(upsilon) boolean AND C consisting of all elements of C within distance one from the vertex upsilon are different. We also require that the sets B(upsilon) boolean AND C are all nonempty. We take G to be the infinite square lattice with diagonals and show that the density of the smallest identifying code is at least 2/9 and at most 4/17.
UTU Research Portal