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。
相关内容
Arxiv
0+阅读 · 2021年3月4日
Arxiv
0+阅读 · 2021年3月2日
相关VIP内容
相关资讯
相关论文
Arxiv
0+阅读 · 2021年3月4日
Arxiv
0+阅读 · 2021年3月2日
微信扫码咨询专知VIP会员