On Markov Chains for Independent Sets
Authors:
- Martin DyerMDMartin Dyer
- Catherine GreenhillCGCatherine Greenhill
- 1 April 2000
- journal article
- Published by Elsevier in Journal of Algorithms
- Vol. 35 (1) , 17-49
Abstract
No abstract availableThis publication has 15 references indexed in Scilit:
- Path coupling: A technique for proving rapid mixing in Markov chains2002
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphscomputational complexity, 2000
- On Approximately Counting Colorings of Small Degree GraphsSIAM Journal on Computing, 1999
- A more rapidly mixing Markov chain for graph coloringsRandom Structures & Algorithms, 1998
- Random walks on generating sets for finite groupsThe Electronic Journal of Combinatorics, 1996
- Logarithmic Sobolev inequalities for finite Markov chainsThe Annals of Applied Probability, 1996
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graphRandom Structures & Algorithms, 1995
- Comparison Theorems for Reversible Markov ChainsThe Annals of Applied Probability, 1993
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Nonlocal Monte Carlo algorithm for self-avoiding walks with fixed endpointsJournal of Statistical Physics, 1990