Connected Identifying Codes

The authors consider the problem of generating a connected identifying code for an arbitrary graph. After a brief motivation, they show that the decision problem regarding the existence of such a code is NP-complete, and they propose a novel polynomial-time approximation ConnectID that transforms any identifying code into a connected version of at most twice the size, thus leading to an asymptotically optimal approximation bound. When the input identifying code to ConnectID is robust to graph distortions, they show that the size of the resulting connected code is related to the best error-correcting code of a given minimum distance, permitting the use of known coding bounds.

Provided by: Boston University Topic: Software Date Added: Mar 2012 Format: PDF

Find By Topic