...researching fundamentals of networking and communications

|

Identifying codes and the set cover problem - 10/06/2006

Moshe Laifenfeld

We consider the problem of finding a minimum identifying code in a graph, i.e., a designated set of vertices whose neighborhoods uniquely overlap atany vertex on the graph. This identifying code problem was initially introduced in 1998 and has been since fundamentally connected to a wide range of applications, including fault diagnosis, location detection, environmental monitoring, and connections to information theory, superimposed codes, and tilings. Though this problem is NP- complete, its known reduction is from 3-SAT and does not readily yield an approximation algorithm. In this paper we show that the identifying code problem is computationally equivalent to the set cover problem and present \Theta(\logn)-approximation algorithm based on the greedy approach for set cover; we further show that, subject to reasonable assumptions, no polynomial-time approximation algorithm can do better.

This is joint work with Ari Trachtenberg and Tanya Berger-Wolf.

r1 - 2008-09-05 - 22:33:16 - WeiyaoXiao

Laboratory of Networking and Information Systems
Photonics Building, Room 413
8 St Mary's Street,
Boston MA 02215


Initial web site created by Sachin Agarwal (ska@alum.bu.edu), Modified by Weiyao Xiao (weiyao@alum.bu.edu), Moved to TWiki backend by Ari Trachtenberg (trachten@bu.edu). Managed by Jiaxi Jin (jin@bu.edu).
Syndicate this site RSSATOM