The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of Adobe Acrobat Reader).

Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.

If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful Frequently Asked Questions about PDFs.

Download this PDF file Fullscreen Fullscreen Off

References

  • Prasad Chebolu, Leslie~Ann Goldberg, and Russell Martin. The complexity of approximately counting stable matchings. In Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques, APPROX/RANDOM'10, pages 81--94, Berlin, Heidelberg, 2010. Springer-Verlag.
  • Dyer, Martin; Frieze, Alan; Jerrum, Mark. On counting independent sets in sparse graphs. SIAM J. Comput. 31 (2002), no. 5, 1527--1541 (electronic). MR1936657
  • Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark. The relative complexity of approximate counting problems. Approximation algorithms. Algorithmica 38 (2004), no. 3, 471--500. MR2044886
  • Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell. Markov chain comparison. Probab. Surv. 3 (2006), 89--111 (electronic). MR2216963
  • Qi~Ge and Daniel Stefankovic. A graph polynomial for independent sets of bipartite graphs. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), volume~8 of Leibniz International Proceedings in Informatics (LIPIcs), pages 240--250, Dagstuhl, Germany, 2010.
  • Goldberg, Leslie Ann; Jerrum, Mark. The complexity of ferromagnetic Ising with local fields. Combin. Probab. Comput. 16 (2007), no. 1, 43--61. MR2286511
  • Jerrum, Mark. Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2003. xii+112 pp. ISBN: 3-7643-6946-9 MR1960003
  • Mitzenmacher, Michael; Upfal, Eli. Probability and computing. Randomized algorithms and probabilistic analysis. Cambridge University Press, Cambridge, 2005. xvi+352 pp. ISBN: 0-521-83540-2 MR2144605
  • Mossel, Elchanan; Weitz, Dror; Wormald, Nicholas. On the hardness of sampling independent sets beyond the tree threshold. Probab. Theory Related Fields 143 (2009), no. 3-4, 401--439. MR2475668
  • Motwani, Rajeev; Raghavan, Prabhakar. Randomized algorithms. Cambridge University Press, Cambridge, 1995. xiv+476 pp. ISBN: 0-521-47465-5 MR1344451
  • Provan, J. Scott; Ball, Michael O. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12 (1983), no. 4, 777--788. MR0721012
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.