On robust and dynamic identifying codes

: Honkala I, Karpovsky MG, Levitin LB

Publisher: IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

: 2006

: IEEE Transactions on Information Theory

: IEEE TRANSACTIONS ON INFORMATION THEORY

: IEEE T INFORM THEORY

: 52

: 2

: 599

: 612

: 14

: 0018-9448

DOI: https://doi.org/10.1109/TIT.2005.862097(external)

A subset C of vertices in an undirected graph G = (V, E) is called a 1-identifying code if the sets I(v) = {u is an element of C : d(u, v) <= 1}, v E V, are nonempty and no two of them are the same set. It is natural to consider classes of codes that retain the identification property under various conditions, e.g., when the sets I(v) are possibly slightly corrupted. We consider two such classes of robust codes. We also consider dynamic identifying codes, i.e., walks in G whose vertices form an identifying code in G.

Mathematics