论文标题
错误纠正识别代码
Error-correcting Identifying Codes
论文作者
论文摘要
假设图形$ g $模拟具有可能“入侵者”的设施的检测系统或具有可能出现故障处理器的多处理器网络。我们考虑将探测器（最小数量）放置在$ g $中的一个子集中（最小数量）的问题，以自动确定是否存在入侵者，如果是这样，则其精确位置。在这项研究中，我们探讨了识别代码的易耐故障变体，即误差校正识别代码，该代码允许一个假阳性或负面，并且适用于现实世界系统。我们提供了确定任意图中确定所述最小大小的问题的NP完整性的证明，并确定立方图中参数的界限。
Assume that a graph $G$ models a detection system for a facility with a possible "intruder," or a multiprocessor network with a possible malfunctioning processor. We consider the problem of placing (the minimum number of) detectors at a subset of vertices in $G$ to automatically determine if there is an intruder, and if so, its precise location. In this research we explore a fault-tolerant variant of identifying codes, known as error-correcting identifying codes, which permit one false positive or negative and are applicable to real-world systems. We present the proof of NP-completeness of the problem of determining said minimum size in arbitrary graphs, and determine bounds on the parameter in cubic graphs.
