Date Added: Dec 2010
Identifying codes have been proposed as an abstraction for implementing monitoring tasks such as indoor localization using wireless sensor networks. In this approach, sensors' radio coverage overlaps in unique ways over each identifiable region, according to the codewords of an identifying code. While connectivity of the underlying identifying code is necessary for routing data to a sink, existing algorithms that produce identifying codes do not guarantee such a property. As such, the authors propose a novel polynomial-time algorithm called ConnectID that transforms any identifying code into a connected version that is also an identifying code and is provably at most twice the size of the original.