论文标题
冗余开放定位套件的NP完整性
The NP-completeness of Redundant Open-Locating-Dominating Set
论文作者
论文摘要
对于图G，主体集D是G中的一个子集，其中G中的每个顶点均在D中或与D中的某些顶点相邻。目的是检测并查明在具有最少传感器数量的系统中入侵者的确切位置。在本文中，我们专注于一个称为冗余旧组的旧组的变体，并提供了冗余旧组问题的NP完整性的证明。
For a graph G, a dominating set D is a subset of vertices in G where each of the vertices in G is in D or adjacent to some vertex in D. An open-locating-dominating (OLD) set models a system with sensors to detect an intruder in a facility or a faulty component in a network of processors. The goal is to detect and pinpoint an intruder's exact location in a system with a minimum number of sensors. In this paper, we focus on a variant of an OLD set called a redundant OLD set and present a proof for the NP-completeness of the problem of a redundant OLD set.
