Identifying codes and location detection system in sensor networks- 06/29/2006

Moshe Laifenfeld

Identifying codes have been studied extensively since their introduction in 1998 (Karpovsky et al., 1998), and have formed a fundamental aspect of a wide variety of theoretical and more practical applications. Intuitively, a radius 1 identifying code is a set of vertices in a graph with the property that each vertex neighborhood in the graph has a unique intersection with the code; the identifying code problem involves finding the identifying code of minimum cardinality for a given graph. From a theoretical perspective, identifying codes are closely linked to error-correcting codes, and the problem in its general version has been shown to be NP-complete. Despite the significant amount of work in the field, only information theoretic and combinatorial bounds or solutions for specific topologies are known thus far.

In our work we broaden our understanding of identifying codes by establishing a reduction to the fundamental and well studied set cover problem. Our reduction is efficient enough to develop a general polynomial approximation with tight performance guarantees for arbitrary directed graphs, based on the well studied greedy set cover heuristic. We further generalize these results to robust identifying codes by linking them to the set multi-cover problem.

In this talk I will also discuss a potential location detection system in sensor networks based on a generalization of identifying codes and their relation to the covering integer problem.