A1 Refereed original research article in a scientific journal
On identifying codes that are robust against edge changes
Authors: Honkala I, Laihonen T
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2007
Journal: Information and Computation
Journal name in source: INFORMATION AND COMPUTATION
Journal acronym: INFORM COMPUT
Volume: 205
Issue: 7
First page : 1078
Last page: 1095
Number of pages: 18
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2007.01.003
Abstract
Assume that G = (V, E) is an undirected graph, and C subset of V. For every v is an element of V, denote I-r(G; v) = {u is an element of C : d(u, v) <= r}, where d(u, v) denotes the number of edges on any shortest path from u to v in G. If all the sets I-r (G; v) for v is an element of V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r=1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide. (c) 2007 Elsevier Inc. All rights reserved.
Assume that G = (V, E) is an undirected graph, and C subset of V. For every v is an element of V, denote I-r(G; v) = {u is an element of C : d(u, v) <= r}, where d(u, v) denotes the number of edges on any shortest path from u to v in G. If all the sets I-r (G; v) for v is an element of V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r=1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide. (c) 2007 Elsevier Inc. All rights reserved.
UTU Research Portal