On a New Class of Codes for Identifying Vertices in Graphs
On a New Class of Codes for Identifying Vertices in Graphs
复制标题
DOI：
10.1109/18.661507
复制
发表时间：
1998-03
期刊：
影响因子：
--
通讯作者：
M. Karpovsky;K. Chakrabarty;L. Levitin
中科院分区：
文献类型：
--
作者：
M. Karpovsky;K. Chakrabarty;L. Levitin
本文研究了一类新的无向图G中顶点的最优覆盖码，使得G中的任何顶点都可以通过检查覆盖它的顶点来唯一地确定.定义一个以顶点/spl upsi/为中心的半径为t的球为G中距离/spl upsi/至多为t的顶点的集合.顶点/spl upsi/然后被说成用中心/spl upsi/覆盖它自己和球中的每一个其他顶点。我们的正式问题陈述如下：给定一个无向图G和一个整数t/spl ges/1，找到一个顶点的（最小）集合C，使得G中的每个顶点属于一个以C中的顶点为中心的半径为t的唯一球集合。由此获得的顶点集构成了用于顶点识别的代码。我们首先发展拓扑独立的边界上的大小C。然后，我们开发的方法构建C的几个特定的拓扑结构，如二进制立方体，nonbinary立方体，树。我们还描述了使用覆盖码，唯一地识别单个顶点的顶点集的识别。我们开发的方法来构建最佳的拓扑结构，产生识别代码的码字的最小数量。最后，我们描述了本文中开发的理论多处理器系统的故障诊断的应用。
We investigate a new class of codes for the optimal covering of vertices in an undirected graph G such that any vertex in G can be uniquely identified by examining the vertices that cover it. We define a ball of radius t centered on a vertex /spl upsi/ to be the set of vertices in G that are at distance at most t from /spl upsi/. The vertex /spl upsi/ is then said to cover itself and every other vertex in the ball with center /spl upsi/. Our formal problem statement is as follows: given an undirected graph G and an integer t/spl ges/1, find a (minimal) set C of vertices such that every vertex in G belongs to a unique set of balls of radius t centered at the vertices in C. The set of vertices thus obtained constitutes a code for vertex identification. We first develop topology-independent bounds on the size of C. We then develop methods for constructing C for several specific topologies such as binary cubes, nonbinary cubes, and trees. We also describe the identification of sets of vertices using covering codes that uniquely identify single vertices. We develop methods for constructing optimal topologies that yield identifying codes with a minimum number of codewords. Finally, we describe an application of the theory developed in this paper to fault diagnosis of multiprocessor systems.