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 \in 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^*({\cal S}_k)$ of an identifying code in the square grid ${\cal S}_k$ of height $k$ (i.e. with vertex set $ \mathbb{Z} \times \{1, \dots , k\}$). Using the Discharging Method, we prove $\displaystyle \frac{7}{20} + \frac{1}{20k} \leq d^*({\cal S}_k) \leq \min \left\{\frac{2}{5}, \frac{7}{20} + \frac{3}{10k} \right\}$, and $\displaystyle d^*({\cal S}_3) =\frac{3}{7}$.
Type de document :
Rapport
[Research Report] RR-8845, INRIA Sophia Antipolis - I3S. 2016
Liste complète des métadonnées


https://hal.inria.fr/hal-01259550
Contributeur : Frederic Havet <>
Soumis le : mercredi 20 janvier 2016 - 15:51:44
Dernière modification le : samedi 17 septembre 2016 - 01:38:19
Document(s) archivé(s) le : jeudi 21 avril 2016 - 11:12:38

Fichier

RR-8845.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01259550, version 1

Collections

Citation

Marwane Bouznif, Frédéric Havet, Myriam Preissmann. Minimum-density identifying codes in square grids. [Research Report] RR-8845, INRIA Sophia Antipolis - I3S. 2016. <hal-01259550>

Partager

Métriques

Consultations de
la notice

225

Téléchargements du document

70