FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
From MaRDI portal
Publication:3620613
DOI10.1142/S0129054109006437zbMath1160.05033OpenAlexW2170912089MaRDI QIDQ3620613
Publication date: 14 April 2009
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054109006437
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Parameterized counting of trees, forests and matroid bases, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for proper interval graph recognition
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- The Computational Complexity of the Tutte Plane: the Bipartite Case
- A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
- On the computational complexity of the Jones and Tutte polynomials
- Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width