DocumentCode
1451459
Title
On codes identifying vertices in the two-dimensional square lattice with diagonals
Author
Cohen, G.D. ; Honkala, L. ; Lobstein, A.
Author_Institution
ENST, CNRS, Paris
Volume
50
Issue
2
fYear
2001
fDate
2/1/2001 12:00:00 AM
Firstpage
174
Lastpage
176
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(v)∩C consisting of all elements of C within distance one from the vertex v are different. We also require that the sets B(v)∩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
Keywords
graph theory; multiprocessor interconnection networks; graph-theoretic definition; identifying code; infinite square lattice; multiprocessor systems; Fault detection; Fault diagnosis; Lattices; Multiprocessing systems; System testing;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.908992
Filename
908992
Link To Document