Computing the Number of k-Component Spanning Forests of a Graph with Bounded Treewidth

作     者：Peng-Fei Wan Xin-Zhuang Chen 

作者机构：Department of Applied MathematicsSchool of ScienceNorthwestern Polytechnical UniversityXi’an 710029China School of Mathematics and StatisticsYulin UniversityYulin 719000ShaanxiChina 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)

年 卷 期：2019年第7卷第2期

页      面：385-394页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：This research was supported by the National Natural Science Foundation of China(Nos.11571135 11671320 and 11601430) 

主　　题：Spanning tree Spanning forest Bounded treewidth Dynamic programming 

摘      要：Let G be a graph on n vertices with bounded *** use fk(G)to denote the number of spanning forests of G with k *** a tree decomposition of width at most p of G,we present an algorithm to compute fk(G)for k=1,2,…,*** running time of our algorithm is O((B(p+1))^(3)pn^(3)),where B(p+1)is the(p+1)-th Bell number.