A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Optimal Local Identifying and Local Locating-dominating Codes
Tekijät: Herva, Pyry; Laihonen, Tero; Lehtilä, Tuomo
Kustantaja: IOS Press BV
Julkaisuvuosi: 2024
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: Fundamenta Informaticae
Vuosikerta: 191
Numero: 3-4
Aloitussivu: 351
Lopetussivu: 378
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-242187
Verkko-osoite: https://doi.org/10.3233/FI-242187
Rinnakkaistallenteen osoite: https://arxiv.org/pdf/2302.13351
Preprintin osoite: https://arxiv.org/abs/2302.13351
Tiivistelmä
We introduce two new classes of covering codes in graphs for every positive integer r. These new codes are called local r-identifying and local r-locating-dominating codes and they are derived from r-identifying and r-locating-dominating codes, respectively. We study the sizes of optimal local 1-identifying codes in binary hypercubes. We obtain lower and upper bounds that are asymptotically tight. Together the bounds show that the cost of changing covering codes into local 1-identifying codes is negligible. For some small n optimal constructions are obtained. Moreover, the upper bound is obtained by a linear code construction. Also, we study the densities of optimal local 1-identifying codes and local 1-locating-dominating codes in the infinite square grid, the hexagonal grid, the triangular grid and the king grid. We prove that seven out of eight of our constructions have optimal densities.
We introduce two new classes of covering codes in graphs for every positive integer r. These new codes are called local r-identifying and local r-locating-dominating codes and they are derived from r-identifying and r-locating-dominating codes, respectively. We study the sizes of optimal local 1-identifying codes in binary hypercubes. We obtain lower and upper bounds that are asymptotically tight. Together the bounds show that the cost of changing covering codes into local 1-identifying codes is negligible. For some small n optimal constructions are obtained. Moreover, the upper bound is obtained by a linear code construction. Also, we study the densities of optimal local 1-identifying codes and local 1-locating-dominating codes in the infinite square grid, the hexagonal grid, the triangular grid and the king grid. We prove that seven out of eight of our constructions have optimal densities.
Julkaisussa olevat rahoitustiedot:
Research supported by the Emil Aaltonen Foundation. Research supported by the Academy of Finland grant 338797.
Turun yliopiston Tutkimustietojärjestelmän portaali