Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T17:31:11.806Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  12 September 2008

J. D. Annan
J. D. Annan
Affiliation:
University College, Oxford e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 3 , September 1994 , pp. 273 - 283
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Annan, J. D. (1994) The complexity of counting problems, D. Phil. Thesis (in preparation), University of Oxford.Google Scholar
[2]Broder, A. Z. (1986) How hard is it to marry at random? (On the approximation of the permanent). Proceedings of the 18th ACM Symposium on Theory of Computing 50–58.Google Scholar
[3]Brooks, R. L., Smith, C. A. B., Stone, A. H. and Tutte, W. H. (1940) The dissection of rectangles into squares. Duke Mathematics Journal 7 312–340.CrossRefGoogle Scholar
[4]Doyle, P. G. and Snell, J. L. (1984) Random walks and electrical networks. Carus Mathematical Monographs 22.Google Scholar
[5]Edwards, K. (1986) The complexity of colouring problems on dense graphs. Theoretical Computer Science 43 337–343.CrossRefGoogle Scholar
[6]Gill, J. (1977) Computational complexity of probabilistic Turing machines. S1AM Journal of Computing 6 675–695.Google Scholar
[7]Jaeger, F., Vertigan, D. L. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Phil. Soc. 108 35–53.CrossRefGoogle Scholar
[8]Jerrum, M. R. and Sinclair, A. J. (1989) Approximating the permanent. SIAM Journal of Computing 18 (6) 1149–1178.CrossRefGoogle Scholar
[9]Jerrum, M. R. and Sinclair, A. J. (1990) Polynomial-time approximation algorithms for the Ising model. (Extended abstract) Proc. 17th ICALP 462–475.Google Scholar
[10]Jerrum, M. R., Valiant, L. G. and Vazirani, V. V. (1986) Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43 169–188.CrossRefGoogle Scholar
[11]Karp, R. M. and Luby, M. (1983) Monte-Carlo algorithms for enumeration and reliability problems. Proc. 24th annual IEEE Symposium on the Foundations of Computer Science 56–64.Google Scholar
[12]Schnorr, C. P. (1976) Optimal algorithms for self-reducible problems. Proc. 3rd ICALP 322–337.Google Scholar
[13]Sinclair, A. J. (1993) Algorithms for random generation and counting: a Markov chain approach, Birkhäuser, Boston.CrossRefGoogle Scholar
[14]Tutte, W. T. (1947) A ring in graph theory. Proceedings of the Cambridge Philosophical Society 43 26–40.CrossRefGoogle Scholar
[15]Vertigan, D. L. and Welsh, D. J. A. (1992) The computational complexity of the Tutte plane: the bipartite case. Combinatorics, Probability and Computing 1 181–187.CrossRefGoogle Scholar
[16]Welsh, D. J. A. (1993) Complexity: Knots, Colourings and Counting London Math. Soc. Lecture Notes 186, Cambridge University Press.Google Scholar
[17]Welsh, D. J. A. (1994) Randomised approximation schemes in the Tutte plane. Combinatorics, Probability and Computing 3 137–143.CrossRefGoogle Scholar