A faster method for sampling independent sets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A faster method for sampling independent sets

Full text

Pdf (180 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 625 - 626

Year of Publication: 2000

ISBN:0-89871-453-2

Author

Mark Huber

Department of Statistics, Stanford University, Stanford, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 22, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	W. Doeblin. Expos6 de la th6orie des chains simples constantes de Markov h un hombre tint d'~tats. Rev. Math. de l'Union Interbalkanique, 2:77-105, 1933.
	2	Martin Dyer, Alan Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. Technical Report ECS-LFCS-98-391, Univ. of Edinburgh, 1998.
	3	Martin Dyer and Catherine GreenhiU. On Markov cJaains for independent sets. Preprint, 1997.
	4	Olle HiiggstrSm and Karin Nelander. Exact sampling from anti-monotone systems, 1997. Preprint.
	5	Mark Huber, Exact sampling and approximate counting techniques, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.31-40, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276709]
	6	Mark Lawrence Huber, Perfect sampling using bounding chains, 1999
	7	M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
	8	James Gary Propp , David Bruce Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures & Algorithms, v.9 n.1-2, p.223-252, Aug./Sept. 1996
	9	Barry Simon. The Statistical Mechanics of Lattice Gasses, volume 1. Princeton University Press, 1993.
	10	Eric Vigoda. Fast convergence of the Glauber dynamics for sampling independent sets: Part II. Technical Report TR-99-003, International Computer Science Institute, January 1998.