Optimality of a 2-identifying code in the hexagonal grid - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Optimality of a 2-identifying code in the hexagonal grid

Junnila Ville
  • Fonction : Auteur
  • PersonId : 905232
Tero Laihonen
  • Fonction : Auteur
  • PersonId : 843771

Résumé

An r-identifying code in a graph G = (V;E) is a subset C V such that for each u 2 V the intersection of C and the ball of radius r centered at u is nonempty and unique. Previously, r-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the hexagonal grid with density 4=19 and that there are no 2-identifying codes with density smaller than 2=11. Recently, the lower bound has been improved to 1=5 by Martin and Stanton (2010). In this paper, we prove that the 2-identifying code with density 4=19 is optimal, i.e. that there does not exist a 2-identifying code in the hexagonal grid with smaller density.
Fichier principal
Vignette du fichier
45.pdf (226.08 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00607289 , version 1 (08-07-2011)

Identifiants

  • HAL Id : inria-00607289 , version 1

Citer

Junnila Ville, Tero Laihonen. Optimality of a 2-identifying code in the hexagonal grid. WCC 2011 - Workshop on coding and cryptography, Apr 2011, Paris, France. pp.47-56. ⟨inria-00607289⟩

Collections

WCC2011 TDS-MACS
63 Consultations
21 Téléchargements

Partager

Gmail Facebook X LinkedIn More