Connected Identifying Codes

Date Added: Mar 2012
Format: PDF

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.