期刊文献+
共找到1篇文章
< 1 >
每页显示 20 50 100
Computing the Number of k-Component Spanning Forests of a Graph with Bounded Treewidth
1
作者 peng-fei wan Xin-Zhuang Chen 《Journal of the Operations Research Society of China》 EI CSCD 2019年第2期385-394,共10页
Let G be a graph on n vertices with bounded treewidth.We use fk(G)to denote the number of spanning forests of G with k components.Given a tree decomposition of width at most p of G,we present an algorithm to compute f... Let G be a graph on n vertices with bounded treewidth.We use fk(G)to denote the number of spanning forests of G with k components.Given a tree decomposition of width at most p of G,we present an algorithm to compute fk(G)for k=1,2,…,n.The running time of our algorithm is O((B(p+1))^(3)pn^(3)),where B(p+1)is the(p+1)-th Bell number. 展开更多
关键词 Spanning tree Spanning forest Bounded treewidth Dynamic programming
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部