We consider the problem of devising algorithms to count exactly the number of independent sets of a graph G . We show that there is a polynomial time algorithm for this problem when G is restricted to the class of strongly orderable graphs, a superclass of chordal bipartite graphs. We also show that such an algorithm exists for graphs of bounded clique-width. Our results extends to a more general setting of counting independent sets in a weighted graph and can be used to count the number of independent sets of any given size k .


翻译:我们考虑了设计算法以精确地计算图G独立数组的问题。我们显示,当G限于强烈有条理的图形类时,这个问题就有一种多元时间算法。G是超等级的极有条理的双边图形。我们还表明,这种算法存在于受约束的圆形图中。我们的结果延伸到一个更笼统的加权图中独立数组设置,可以用来计算任何特定大小的独立的K。

0
下载
关闭预览

相关内容

【知识图谱@EMNLP2020】Knowledge Graphs in NLP @ EMNLP 2020
专知会员服务
40+阅读 · 2020年11月22日
【干货书】机器学习速查手册,135页pdf
专知会员服务
120+阅读 · 2020年11月20日
最新《图神经网络知识图谱补全》综述论文
专知会员服务
153+阅读 · 2020年7月29日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
已删除
将门创投
3+阅读 · 2019年10月18日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年3月4日
Arxiv
0+阅读 · 2021年3月4日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
VIP会员
相关VIP内容
【知识图谱@EMNLP2020】Knowledge Graphs in NLP @ EMNLP 2020
专知会员服务
40+阅读 · 2020年11月22日
【干货书】机器学习速查手册,135页pdf
专知会员服务
120+阅读 · 2020年11月20日
最新《图神经网络知识图谱补全》综述论文
专知会员服务
153+阅读 · 2020年7月29日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
相关资讯
已删除
将门创投
3+阅读 · 2019年10月18日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员