A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs

1994/09/01 by J. D. Annan · 1 citation
Computer Science · Mathematics · #Algorithm #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph Theory and Algorithms #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Polynomial #Polynomial-time approximation scheme #Scheme (mathematics) #Time complexity

paper · doi:10.1017/s0963548300001188

openalex publication_date 1994/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

Abstract

A polynomial-time randomised algorithm for uniformly generating forests in a dense graph is presented. Using this, a fully polynomial randomised approximation scheme (fpras) for counting the number of forests in a dense graph is created.

Citations

• On the computational complexity of the Jones and Tutte polynomials
• The dissection of rectangles into squares
• Computational Complexity of Probabilistic Turing Machines
• Algorithms for Random Generation and Counting: A Markov Chain Approach
• The Computational Complexity of the Tutte Plane: the Bipartite Case

Cited by

• Tutte polynomial [wikipedia]