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.展开更多
基金This research was supported by the National Natural Science Foundation of China(Nos.11571135,11671320 and 11601430).
文摘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.
