FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES

DOI10.1142/S0129054109006437zbMath1160.05033OpenAlexW2170912089MaRDI QIDQ3620613

Heidi Gebauer, Yoshio Okamoto

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

Mathematics Subject Classification ID

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