A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On identifying codes in the king grid that are robust against edge deletions
Tekijät: Honkala I, Laihonen T
Kustantaja: ELECTRONIC JOURNAL OF COMBINATORICS
Julkaisuvuosi: 2008
Journal: The Electronic Journal of Combinatorics
Tietokannassa oleva lehden nimi: ELECTRONIC JOURNAL OF COMBINATORICS
Lehden akronyymi: ELECTRON J COMB
Vuosikerta: 15
Numero: 1
Sivujen määrä: 13
ISSN: 1077-8926
Tiivistelmä
Assume that G = (V,E) is an undirected graph, C subset of V. For every v is an element of V we 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. 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. If C is r-identifying in all graphs G' that can be obtained form G by deleting at most t edges, we say that C is robust against t known edge deletions. Codes that are robust against t unknown edge deletions form a related class. We study these two classes of codes in the king grid with the vertex set Z(2) where two different vertices are adjacent if their Euclidean distance is at most root 2.
Assume that G = (V,E) is an undirected graph, C subset of V. For every v is an element of V we 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. 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. If C is r-identifying in all graphs G' that can be obtained form G by deleting at most t edges, we say that C is robust against t known edge deletions. Codes that are robust against t unknown edge deletions form a related class. We study these two classes of codes in the king grid with the vertex set Z(2) where two different vertices are adjacent if their Euclidean distance is at most root 2.
Turun yliopiston Tutkimustietojärjestelmän portaali