×

zbMATH — the first resource for mathematics

A randomised approximation algorithm for counting the number of forests in dense graphs. (English) Zbl 0809.05086
A polynomial-time randomised algorithm for uniformly generating forests in a dense graph is presented. Using this, a fully polynomial randomised approximation scheme for counting the number of forests in a dense graph is created.
Reviewer: J.D.Annan (Oxford)

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
05C30 Enumeration in graph theory
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Doyle, Carus Mathematical Monographs 22 (1984)
[2] DOI: 10.1016/0304-3975(86)90184-2 · Zbl 0597.68038 · doi:10.1016/0304-3975(86)90184-2
[3] Broder, Proceedings of the 18th ACM Symposium on Theory of Computing pp 50– (1986)
[4] DOI: 10.1017/S0963548300001036 · Zbl 0811.68105 · doi:10.1017/S0963548300001036
[5] Welsh, London Math. Soc. Lecture Notes pp 186– (1993)
[6] DOI: 10.1017/S0963548300000195 · Zbl 0793.05091 · doi:10.1017/S0963548300000195
[7] DOI: 10.1017/S0305004100023173 · doi:10.1017/S0305004100023173
[8] Sinclair, Algorithms for random generation and counting: a Markov chain approach (1993) · Zbl 0780.68096 · doi:10.1007/978-1-4612-0323-0
[9] Schnorr, Proc. 3rd ICALP pp 322– (1976)
[10] Karp, Proc. 24th annual IEEE Symposium on the Foundations of Computer Science pp 56– (1983)
[11] Jerrum, Proc. 17th ICALP pp 462– (1990)
[12] DOI: 10.1016/0304-3975(86)90174-X · Zbl 0597.68056 · doi:10.1016/0304-3975(86)90174-X
[13] DOI: 10.1137/0218077 · Zbl 0723.05107 · doi:10.1137/0218077
[14] DOI: 10.1017/S0305004100068936 · Zbl 0747.57006 · doi:10.1017/S0305004100068936
[15] DOI: 10.1137/0206049 · Zbl 0366.02024 · doi:10.1137/0206049
[16] DOI: 10.1215/S0012-7094-40-00718-9 · Zbl 0024.16501 · doi:10.1215/S0012-7094-40-00718-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.