A detection system, modeled in a graph, is composed of "detectors" positioned at a subset of vertices in order to uniquely locate an ``intruder" at any vertex. \emph{Identifying codes} use detectors that can sense the presence or absence of an intruder within distance one. We introduce a fault-tolerant identifying code called a \emph{redundant identifying code}, which allows at most one detector to go offline or be removed without disrupting the detection system. In real-world applications, this would be a necessary feature, as it would allow for maintenance on individual components without disabling the entire system. Specifically, we prove that the problem of determining the lowest cardinality of an identifying code for an arbitrary graph is NP-complete, we determine the bounds on the lowest cardinality for special classes of graphs, including trees, cylinders, and cubic graphs.
翻译:以图示为模型的探测系统由“ 检测器” 组成, 位于一个脊椎子子组, 以在任何顶端独有定位“ 入侵器” 。\ emph{ 识别代码} 使用能够感知到某一距离内入侵者的存在或不存在的检测器。 我们引入了一种称为 emph{ redundant 识别代码 的防故障识别代码, 最多允许一个检测器离线或被移除而不会干扰检测系统。 在现实世界应用中, 这将是一个必要的特征, 因为它允许在不破坏整个系统的情况下对单个部件进行维护 。 具体地说, 我们证明, 确定任意图形识别代码的最低基点问题是 NP 完整的, 我们决定了特殊图表类别, 包括树木、 气瓶和 立方图的最小基点的界限 。