Ville Junnila - Adaptive Identification of Sets of Vertices in Graphs

dmtcs:574 - Discrete Mathematics & Theoretical Computer Science, April 17, 2012, Vol. 14 no. 1 - https://doi.org/10.46298/dmtcs.574
Adaptive Identification of Sets of Vertices in GraphsArticle

Authors: Ville Junnila ORCID1

  • 1 Department of Mathematics

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.


Volume: Vol. 14 no. 1
Section: Combinatorics
Published on: April 17, 2012
Accepted on: June 9, 2015
Submitted on: November 25, 2008
Keywords: Identifying codes,Adaptive identification,Fault-detection,Sensor networks,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 368 times.
This article's PDF has been downloaded 279 times.