The d-identifying codes problem for vertex identification in graphs: Probabilistic analysis and an approximation algorithm
The d-identifying codes problem for vertex identification in graphs: Probabilistic analysis and an approximation algorithm
Given a graph G(V, E), the identifying codes problem is to find the smallest set of vertices D ⊆ V such that no two vertices in V are adjacent to the same set of vertices in D. The identifying codes problem has been applied to fault diagnosis and sensor based location detection in harsh environments. In this paper, we introduce and study a generalization of this problem, namely, the d-identifying codes problem. We propose a polynomial time approximation algorithm based on ideas from information theory and establish its approximation ratio that is very close to the best possible. Using analysis on random graphs, several fundamental properties of the optimal solution to this problem are also derived. © Springer-Verlag Berlin Heidelberg 2006.
Journal Article
4112 LNCS
284
298
- University of Cyprus Cyprus
Information theory, Sensors, Code problems, Approximation theory, Codes (symbols), Probabilistic logics, Polynomials, Tracking (position), Graphic methods, Polynomial time approximation algorithms, Algorithms, Fault diagnosis, Random graphs
Information theory, Sensors, Code problems, Approximation theory, Codes (symbols), Probabilistic logics, Polynomials, Tracking (position), Graphic methods, Polynomial time approximation algorithms, Algorithms, Fault diagnosis, Random graphs
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!