Minimum-Density Identifying Codes in Square Grids

Marwane Bouznif 1 Frédéric Havet 2 Myriam Preissmann 1
1 G-SCOP_OC - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : An identifying code in a graph G is a subset of vertices with the property that for each vertex v ∈ V (G), the collection of elements of C at distance at most 1 from v is non-empty and distinct from the collection of any other vertex. We consider the minimum density d * (S k) of an identifying code in the square grid S k of height k (i.e. with vertex set Z × {1,. .. , k}). Using the Discharging Method, we prove 7 20 + 1 20k ≤ d * (S k) ≤ min 2 5 , 7 20 + 3 10k , and d * (S3) = 7 18 .
Type de document :
Communication dans un congrès
11th International Conference, AAIM 2016, Jul 2016, Bergamo, Italy. Springer, 9778, pp.77-88, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-41168-2_7〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01346750
Contributeur : Frederic Havet <>
Soumis le : mardi 19 juillet 2016 - 15:14:22
Dernière modification le : mardi 26 juillet 2016 - 15:06:14

Fichier

AAIM-grid-code.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Marwane Bouznif, Frédéric Havet, Myriam Preissmann. Minimum-Density Identifying Codes in Square Grids. 11th International Conference, AAIM 2016, Jul 2016, Bergamo, Italy. Springer, 9778, pp.77-88, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-41168-2_7〉. 〈hal-01346750〉

Partager

Métriques

Consultations de
la notice

144

Téléchargements du document

41