Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PATH COUPLING:
Reports tagged with Path coupling:
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 >>>

TR05-151 | 7th December 2005
Magnus Bordewich, Martin Dyer, Marek Karpinski

#### Metric Construction, Stopping Times and Path Coupling.

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... more >>>

ISSN 1433-8092 | Imprint