Optimality of a 2-identifying code in the hexagonal grid

Abstract : 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.
Type de document :
Communication dans un congrès
WCC 2011 - Workshop on coding and cryptography, Apr 2011, Paris, France. pp.47-56, 2011
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00607289
Contributeur : Assia Saadi <>
Soumis le : vendredi 8 juillet 2011 - 14:16:49
Dernière modification le : mercredi 29 novembre 2017 - 10:27:33
Document(s) archivé(s) le : lundi 12 novembre 2012 - 10:31:10

Fichier

45.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00607289, version 1

Collections

Citation

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, 2011. 〈inria-00607289〉

Partager

Métriques

Consultations de la notice

109

Téléchargements de fichiers

42