论文标题
具有错误校正的耐故障定位式设置
Fault-Tolerant Locating-Dominating sets with Error-correction
论文作者
论文摘要
定位式集合是代表图G中“检测器”的顶点的子集；每个探测器都监视其封闭的邻域，并可以将自己的位置与邻居区分开，并鉴于所有传感器输入，系统可以在图中的任何地方找到一个“入侵者”。我们探讨了定位符合式集合的易于故障的变体，错误校正校正定位（err：ld）集，该集可以忍受来自单个检测器的错误信号。特别是，我们表征了误差校正定位的集合，并得出其存在标准。我们还证明，在任意图中确定err：ld的最小基数的问题是NP完整的。此外，我们为无限网格和立方图的ERR：LD集的最小密度建立了下限和上限，并证明了立方图的下限。
A locating-dominating set is a subset of vertices representing "detectors" in a graph G; each detector monitors its closed neighborhood and can distinguish its own location from its neighbors, and given all sensor input, the system can locate an "intruder" anywhere in the graph. We explore a fault-tolerant variant of locating-dominating sets, error-correcting locating-dominating (ERR:LD) sets, which can tolerate an incorrect signal from a single detector. In particular, we characterize error-correcting locating-dominating sets, and derive its existence criteria. We also prove that the problem of determining the minimum cardinality of ERR:LD set in arbitrary graphs is NP-complete. Additionally, we establish lower and upper bounds for the minimum density of ERR:LD sets in infinite grids and cubic graphs, and prove the lower bound for cubic graphs is sharp.
