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。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
和积网络综述论文,Sum-product networks: A survey,24页pdf
专知会员服务
23+阅读 · 2020年4月3日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【 关关的刷题日记47】Leetcode 38. Count and Say
【LeetCode 136】 关关的刷题日记32 Single Number
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年12月3日
Arxiv
0+阅读 · 2021年12月3日
Arxiv
14+阅读 · 2019年9月11日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
和积网络综述论文,Sum-product networks: A survey,24页pdf
专知会员服务
23+阅读 · 2020年4月3日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【 关关的刷题日记47】Leetcode 38. Count and Say
【LeetCode 136】 关关的刷题日记32 Single Number
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员