Adaptive Identification of Sets of Vertices in Graphs

Abstract : In this paper, we consider a concept of adaptive identification of vertices and sets of vertices in different graphs, which was recently introduced by Ben-Haim, Gravier, Lobstein and Moncel (2008). The motivation for adaptive identification comes from applications such as sensor networks and fault detection in multiprocessor systems. We present an optimal adaptive algorithm for identifying vertices in cycles. We also give efficient adaptive algorithms for identifying sets of vertices in different graphs such as cycles, king lattices and square lattices. Adaptive identification is also considered in Hamming spaces, which is one of the most widely studied graphs in the field of identifying codes.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 1 (1), pp.69-86
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990571
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:19:47
Dernière modification le : jeudi 7 septembre 2017 - 01:03:39
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:33:44

Fichier

1098-6878-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990571, version 1

Collections

Citation

Ville Junnila. Adaptive Identification of Sets of Vertices in Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 1 (1), pp.69-86. 〈hal-00990571〉

Partager

Métriques

Consultations de la notice

55

Téléchargements de fichiers

114