A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Locating vertices using codes
Tekijät: Exoo G, Junnila V, Laihonen T, Ranto S
Kustantaja: Utilitas Mathematica Publishing Inc.
Julkaisuvuosi: 2008
Journal: Congressus Numerantium
Vuosikerta: 191
Aloitussivu: 143
Lopetussivu: 159
Sivujen määrä: 17
Tiivistelmä
A nonempty subset of the vertices (called words) of a binary n-dimensional hypercube is called an r-locating-dominating code if for every non-codeword the set of codewords within distance r from it is nonempty and different. An r-locating-dominating code is r-identifying if the condition holds for all words (not only
non-codewords). The smallest possible cardinality of an r-identifying code of dimension n is denoted by M_r(n). It is an open problem whether M_{r+s}(n+m)\le M_r(n)M_s(m) holds. We show that when m is relatively small compared to n the
conjecture holds. We also prove similar results for the cardinalities of codes identifying sets of vertices. We give constructions and lower bounds for r-locating-dominating codes.
A nonempty subset of the vertices (called words) of a binary n-dimensional hypercube is called an r-locating-dominating code if for every non-codeword the set of codewords within distance r from it is nonempty and different. An r-locating-dominating code is r-identifying if the condition holds for all words (not only
non-codewords). The smallest possible cardinality of an r-identifying code of dimension n is denoted by M_r(n). It is an open problem whether M_{r+s}(n+m)\le M_r(n)M_s(m) holds. We show that when m is relatively small compared to n the
conjecture holds. We also prove similar results for the cardinalities of codes identifying sets of vertices. We give constructions and lower bounds for r-locating-dominating codes.
Turun yliopiston Tutkimustietojärjestelmän portaali