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 , Laboratoire I3S - 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 .
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01346750
Contributor : Frederic Havet <>
Submitted on : Tuesday, July 19, 2016 - 3:14:22 PM
Last modification on : Monday, April 8, 2019 - 10:28:52 AM

File

AAIM-grid-code.pdf
Files produced by the author(s)

Identifiers

Citation

Marwane Bouznif, Frédéric Havet, Myriam Preissmann. Minimum-Density Identifying Codes in Square Grids. 11th International Conference, AAIM 2016, Riccardo Dondi, Jul 2016, Bergamo, Italy. pp.77-88, ⟨10.1007/978-3-319-41168-2_7⟩. ⟨hal-01346750⟩

Share

Metrics

Record views

285

Files downloads

62