Adaptive Identification of Sets of Vertices in Graphs
Ville Junnila
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.
Full Text: PDF PostScript