论文标题
在冗余定位集合中
On Redundant Locating-Dominating Sets
论文作者
论文摘要
图G中的定位集合是代表“探测器”的顶点的子集，鉴于每个检测器覆盖其封闭的邻域并可以将其自己的位置与邻居区分开来，可以定位“入侵者”。我们探索了一个易于故障的定位式变体，称为冗余定位式集合，该集合可以忍受一个检测器故障（离线或被删除）。特别是，我们表征了冗余定位集合集，并证明确定冗余定位统计组的最小基数的问题是NP完整的。我们还确定了在几类图形中的冗余定位集合的最小密度的紧密界限，包括路径，循环，梯子，K-Ary树以及无限的六角形和三角形网格。我们发现，对于所有订单$ n $的树木的最小冗余定位式集合的大小，下层和上限都紧密，并描述了实现这两个极值值的树木家族，以及多项式时间算法，以将树分类为最低限度。
A locating-dominating set in a graph G is a subset of vertices representing "detectors" which can locate an "intruder" given that each detector covers its closed neighborhood and can distinguish its own location from its neighbors. We explore a fault-tolerant variant of locating-dominating sets called redundant locating-dominating sets, which can tolerate one detector malfunctioning (going offline or being removed). In particular, we characterize redundant locating-dominating sets and prove that the problem of determining the minimum cardinality of a redundant locating-dominating set is NP-complete. We also determine tight bounds for the minimum density of redundant locating-dominating sets in several classes of graphs including paths, cycles, ladders, k-ary trees, and the infinite hexagonal and triangular grids. We find tight lower and upper bounds on the size of minimum redundant locating-dominating sets for all trees of order $n$, and characterize the family of trees which achieve these two extremal values, along with polynomial time algorithms to classify a tree as minimum extremal or not.
