On Markov Chains for Independent Sets
โ
Martin Dyer; Catherine Greenhill
๐
Article
๐
2000
๐
Elsevier Science
๐
English
โ 219 KB
Random independent sets in graphs arise, for example, in statistical physics, in the hardcore model of a gas. In 1997, Luby and Vigoda described a rapidly mixing Markov chain for independent sets, which we refer to as the LubyแVigoda chain. A new rapidly mixing Markov chain for independent sets is d