论文标题
在（折叠）超管中的最小双重解决设置问题与硬币称重问题之间的桥梁之间的桥梁
A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem
论文作者
论文摘要
在本文中，我们考虑了在锤子图，超管和折叠式高管中最小的双重解析集问题。我们证明，超纤维中的最小双重解决问题相当于硬币称重问题。然后，我们回答了一个关于超级方块中最小的双重解决集问题的开放问题。我们在折叠的高管中就度量维度问题解释了一个猜想，并通过在这些问题之间建立锤子图和折叠的高管中的度量尺寸和最小的双重分辨率问题给出了一些渐近结果。使用Lindström的硬币称重问题的方法，我们为高管中的最小双重解析设置问题提供了有效的算法，并报告了一些新的上限。我们还证明，最小的双重解析集问题是NP-甚至限制了拆分图，两部分图和联合三角图。
In this paper, we consider the minimal doubly resolving set problem in Hamming graphs, hypercubes and folded hypercubes. We prove that the minimal doubly resolving set problem in hypercubes is equivalent to the coin weighing problem. Then we answer an open question on the minimal doubly resolving set problem in hypercubes. We disprove a conjecture on the metric dimension problem in folded hypercubes and give some asymptotic results for the metric dimension and the minimal doubly resolving set problems in Hamming graphs and folded hypercubes by establishing connections between these problems. Using the Lindström's method for the coin weighing problem, we give an efficient algorithm for the minimal doubly resolving set problem in hypercubes and report some new upper bounds. We also prove that the minimal doubly resolving set problem is NP-hard even restrict on split graphs, bipartite graphs and co-bipartite graphs.
