Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth

DOI10.1007/s40305-019-00241-4zbMath1438.05044OpenAlexW2918980395MaRDI QIDQ2314068

Pengfei Wan, Xinzhuang Chen

Publication date: 19 July 2019

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40305-019-00241-4

zbMATH Keywords

dynamic programmingspanning treebounded treewidthspanning forest

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• ComputeTW
• tutte_bhkk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The asymptotic number of spanning forests of complete bipartite labelled graphs
• Treewidth computations. I: Upper bounds
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs
• New method for counting the number of spanning trees in a two-tree network
• The number of spanning forests of a graph
• Uniform spanning forests
• Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The number of spanning trees in Apollonian networks
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
• Graph minors. II. Algorithmic aspects of tree-width
• Enumeration of Forests in a Graph
• Countingk-component forests of a graph
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• On the computational complexity of the Jones and Tutte polynomials
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the spanning tree packing number of a graph: A survey

This page was built for publication: Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth