dc.contributor.author | Xiao, Y. | en |
dc.contributor.author | Hadjicostis, Christoforos N. | en |
dc.contributor.author | Thulasiraman, K. | en |
dc.creator | Xiao, Y. | en |
dc.creator | Hadjicostis, Christoforos N. | en |
dc.creator | Thulasiraman, K. | en |
dc.date.accessioned | 2019-04-08T07:48:45Z | |
dc.date.available | 2019-04-08T07:48:45Z | |
dc.date.issued | 2006 | |
dc.identifier.issn | 3-540-36925-2 | |
dc.identifier.issn | 978-3-540-36925-7 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/45105 | |
dc.description.abstract | 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. | en |
dc.source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-33749582618&partnerID=40&md5=a06bb85b9cb1b862679b4f4f810d15cf | |
dc.subject | Information theory | en |
dc.subject | Algorithms | en |
dc.subject | Approximation theory | en |
dc.subject | Probabilistic logics | en |
dc.subject | Sensors | en |
dc.subject | Codes (symbols) | en |
dc.subject | Polynomials | en |
dc.subject | Fault diagnosis | en |
dc.subject | Graphic methods | en |
dc.subject | Tracking (position) | en |
dc.subject | Code problems | en |
dc.subject | Polynomial time approximation algorithms | en |
dc.subject | Random graphs | en |
dc.title | The d-identifying codes problem for vertex identification in graphs: Probabilistic analysis and an approximation algorithm | en |
dc.type | info:eu-repo/semantics/article | |
dc.description.volume | 4112 LNCS | en |
dc.description.issue | Journal Article | en |
dc.description.startingpage | 284 | |
dc.description.endingpage | 298 | |
dc.author.faculty | Πολυτεχνική Σχολή / Faculty of Engineering | |
dc.author.department | Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών / Department of Electrical and Computer Engineering | |
dc.type.uhtype | Article | en |
dc.source.abbreviation | Lect. Notes Comput. Sci. | en |
dc.contributor.orcid | Hadjicostis, Christoforos N. [0000-0002-1706-708X] | |
dc.gnosis.orcid | 0000-0002-1706-708X | |