We consider Upper Domination, the problem of finding the minimal dominating set of maximum cardinality. Very few exact algorithms have been described for solving Upper Domination. In particular, no binary programming formulations for Upper Domination have been described in literature, although such formulations have proved quite successful for other kinds of domination problems. We introduce two such binary programming formulations, and compare their performance on various kinds of graphs. We demonstrate that the first performs better in most cases, but the second performs better for very sparse graphs. Also included is a short proof that the upper domination of any generalized Petersen graph P(n,k) is equal to n.
翻译:我们考虑的是 " 上限 " 问题,即找到最起码的支配性最大基点组的问题。在解决 " 上限 " 方面,没有描述多少精确的算法。特别是,文献中没有描述过 " 上限 " 的二进制程序配方,尽管对于其他类型的支配性问题,这种配方证明相当成功。我们引入了两种这样的二进制程序配方,并在各种图表上比较了它们的性能。我们证明,在多数情况下,第一种效果更好,但第二种效果对非常稀少的图表更好。还包含一个简短的证据,证明任何通用的彼得森图P(n,k)的上层占优势等于 n。