Adaptive Identification of Sets of Vertices in Graphs

: Junnila V

Publisher: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE

: 2012

: Discrete Mathematics and Theoretical Computer Science

: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE

: DISCRETE MATH THEOR

: 1

: 14

: 1

: 69

: 86

: 18

: 1462-7264

: https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1098.1.html

: https://research.utu.fi/converis/portal/detail/Publication/3809048

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.

AdaptiveIdentificationFinalDMTCS.pdf