A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On identifying codes that are robust against edge changes
Tekijät: Honkala I, Laihonen T
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2007
Journal: Information and Computation
Tietokannassa oleva lehden nimi: INFORMATION AND COMPUTATION
Lehden akronyymi: INFORM COMPUT
Vuosikerta: 205
Numero: 7
Aloitussivu: 1078
Lopetussivu: 1095
Sivujen määrä: 18
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2007.01.003
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali