We prove constructively that the maximum possible number of minimal connected dominating sets in a connected undirected graph of order $n$ is in $\Omega(1.489^n)$. This improves the previously known lower bound of $\Omega(1.4422^n)$ and reduces the gap between lower and upper bounds for input-sensitive enumeration of minimal connected dominating sets in general graphs as well as some special graph classes.


翻译:我们建设性地证明,在一个链接的无方向的顺序图中,最起码的连接占支配地位的组数以美元表示(1.489美元),这改进了以前已知的较低约束值(1.44222美元),并缩小了一般图表中输入敏感度最小连接占支配地位组数以及某些特殊图表类别中输入敏感度组数的下限和上限值之间的差距。

0
下载
关闭预览

相关内容

神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
74+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
253+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
60+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
31+阅读 · 2019年10月17日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
保序最优传输:Order-preserving Optimal Transport
我爱读PAMI
6+阅读 · 2018年9月16日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Arxiv
0+阅读 · 2021年12月24日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关VIP内容
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
74+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
253+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
60+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
31+阅读 · 2019年10月17日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
保序最优传输:Order-preserving Optimal Transport
我爱读PAMI
6+阅读 · 2018年9月16日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Top
微信扫码咨询专知VIP会员