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

DOI10.1017/S0963548300001188zbMath0809.05086OpenAlexW2108932844WikidataQ60264976 ScholiaQ60264976MaRDI QIDQ4314146

J. D. Annan

Publication date: 20 November 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300001188

zbMATH Keywords

dense graphrandomised approximation schemecounting the number of forestsrandomised approximation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Combinatorial probability (60C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Unnamed Item ⋮ Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case ⋮ Models of random subtrees of a graph ⋮ Geometric bounds on the fastest mixing Markov chain ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ The Tutte polynomial modulo a prime ⋮ The Potts model and the Tutte polynomial ⋮ FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES ⋮ Spanning tree constrained determinantal point processes are hard to (approximately) evaluate ⋮ Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph ⋮ Negative association in uniform forests and connected graphs ⋮ The polytope of win vectors ⋮ A weighted graph polynomial from chromatic invariants of knots ⋮ Forests, colorings and acyclic orientations of the square lattice

Cites Work

• Unnamed Item
• The complexity of colouring problems on dense graphs
• Random generation of combinatorial structures from a uniform distribution
• The dissection of rectangles into squares
• Approximating the Permanent
• Computational Complexity of Probabilistic Turing Machines
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Randomised Approximation in the Tutte Plane
• On the computational complexity of the Jones and Tutte polynomials

This page was built for publication: A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs