Identifying codes in (random) unit disk graphs

Tobias Muller

Technical University Eindhoven

Abstract

If G is a graph and C is a subset of the vertices of G, then the shadow of a vertex v on C is the intersection of the closed neighbourhood of v with C. For a set A of the vertex set the shadow is the union of the shadows of its elements.

The set C is an l-identifying code, if the shadows of all sets of cardinality at most l are distinct. Identifying codes are used in application such as "fault diagnosis in multiprocessor systems", detecting of computer virusses and "location detection in harsh environments". Motivated by this last application we study identifying codes in unit disk graphs. We study the complexity of finding a minimum identifying code and we consider identifying codes in randomly generated unit disk graphs. The probabilistic results are in stark contrast with results by Frieze et al. (2005) on identifying codes in the Erdos-Renyi model.

(joint work