A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On a new class of identifying codes in graphs
Tekijät: Honkala I, Laihonen T
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2007
Journal: Information Processing Letters
Tietokannassa oleva lehden nimi: INFORMATION PROCESSING LETTERS
Lehden akronyymi: INFORM PROCESS LETT
Vuosikerta: 102
Numero: 2-3
Aloitussivu: 92
Lopetussivu: 98
Sivujen määrä: 7
ISSN: 0020-0190
DOI: https://doi.org/10.1016/j.ipl.2006.11.007
Tiivistelmä
Assume that G = (V, E) is an undirected graph, and C subset of V. For every v is an element of V, we denote I-r(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. For every F subset of V, we denote I-r(F) = boolean OR(v is an element of F) I-r(v). We study codes C with the property that if I-r(F) = I-r(F') and F not equal F', then both F and F' have size at least l + 1. Such codes can be used in the maintenance of multiprocessor architectures. We consider the cases when G is the infinite square or king grid, infinite triangular lattice or hexagonal mesh, or a binary hypercube. (c) 2006 Elsevier B.V. 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, we denote I-r(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. For every F subset of V, we denote I-r(F) = boolean OR(v is an element of F) I-r(v). We study codes C with the property that if I-r(F) = I-r(F') and F not equal F', then both F and F' have size at least l + 1. Such codes can be used in the maintenance of multiprocessor architectures. We consider the cases when G is the infinite square or king grid, infinite triangular lattice or hexagonal mesh, or a binary hypercube. (c) 2006 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali