Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990571
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 4:19:47 PM
Last modification on : Thursday, September 7, 2017 - 1:03:39 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:33:44 PM

File

1098-6878-1-PB.pdf
Files produced by the author(s)

Identifiers

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. ⟨10.46298/dmtcs.574⟩. ⟨hal-00990571⟩

Share

Metrics

Record views

29

Files downloads

555