The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
From MaRDI portal
Publication:3591342
DOI10.1007/11809678_31zbMath1162.05363MaRDI QIDQ3591342
Krishnaiyan Thulasiraman, Christoforos N. Hadjicostis, Y. Xiao
Publication date: 10 September 2007
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11809678_31
68W40: Analysis of algorithms
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Almost Every n-Vertex Graph is Determined by Its 3log2n-Vertex Subgraphs, Upper bounds for binary identifying codes, Fault tolerance of hypercube like networks: spanning laceability under edge faults, Locating-Domination and Identification