首页 | 本学科首页   官方微博 | 高级检索  
     


On identifying codes that are robust against edge changes
Affiliation:Department of Mathematics, University of Turku, 20014 Turku, Finland
Abstract:Assume that G = (V, E) is an undirected graph, and C  V. For every v  V, denote Ir(G; v) = {u  C: d(u,v)  r}, where d(u,v) denotes the number of edges on any shortest path from u to v in G. If all the sets Ir(G; v) for v  V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r = 1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号