Identifying Codes and Location Detection - 02/14/2002

Saikat Ray and Rachanee Ungrangsi

An identifying code 'C' is a subset of nodes of a graph so that for any node 'u' in the graph, the set of nodes in 'C' that are adjacent to 'u' is unique. Previously, a centralized algorithm was developed by us that computes an irreducible identifying code for any graph (the optimal code construction problem is NP-complete). Recently, we have developed a distributed version of the algorithm. In this presentation, I will describe this new algorithm and discuss its performance and some merits as well as weaknesses. Our work on identifying code is motivated by its application in location detection schemes using sensors. Recently, Peary has come up with a simple proof-of-concept testbed of our scheme. In the second half of the talk, she will describe the testbed and present statistical data that characterizes it.