Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with stopping time:
TR05-002 | 6th January 2005
Magnus Bordewich, Martin Dyer, Marek Karpinski

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

We give a new method for analysing the mixing time of a Markov chain using
path coupling with stopping times. We apply this approach to two hypergraph
problems. We show that the Glauber dynamics for independent sets in a
hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ... more >>>

ISSN 1433-8092 | Imprint