Boston University  Engineering Home  Electrical & Computer Engineering  Contact us 

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 NPcomplete). 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 proofofconcept testbed of our scheme. In the second half of the talk, she will describe the testbed and present statistical data that characterizes it.
Lab of Networking and Information Systems Room 413 Photonics Building 8 St Mary's Street, Boston MA 02215
Web site created by Sachin Agarwal (ska@bu.edu)
