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

Magnus Bordewich, Martin Dyer, Marek Karpiński

Type: Article

Publication Date: 2005-01-01

Citations: 2

Locations

Electronic colloquium on computational complexity - View

Similar Works

Action	Title	Year	Authors
+	Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs	2005	Magnus Bordewich Martin Dyer Marek Karpiński
+	Path Coupling Using Stopping Times	2005	Magnus Bordewich Martin Dyer Marek Karpiński
+	Metric Construction, Stopping Times and Path Coupling	2005	Magnus Bordewich Martin Dyer Marek Karpiński
+	Path coupling using stopping times and counting independent sets and colorings in hypergraphs	2008	Magnus Bordewich Martin Dyer Marek Karpiński
+	Stopping Times, Metrics and Approximate Counting	2006	Magnus Bordewich Martin Dyer Marek Karpiński
+	Metric Construction, Stopping Times and Path Coupling	2005	Magnus Bordewich Martin Dyer Marek Karpiński
+	An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings	2001	Martin Dyer Leslie Ann Goldberg Catherine Greenhill Mark Jerrum Michael Mitzenmacher
+	Rapid mixing for the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs	2021	David Eppstein Daniel Frishberg
+	Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs.	2021	David Eppstein Daniel Frishberg
+ PDF Chat	Path coupling: A technique for proving rapid mixing in Markov chains	2002	Russ Bubley Martin Dyer
+	Counting Independent Sets in Hypergraphs when Strong Spatial Mixing Fails	2015	Ivona Bezáková Andreas Galanis Leslie Ann Goldberg Heng Guo Daniel Štefankovič
+	Mixing of Markov Chains for Independent Sets on Chordal Graphs with Bounded Separators	2020	Ivona Bezáková Wenbo Sun
+	On Approximately Counting Colorings of Small Degree Graphs	1999	Russ Bubley Martin Dyer Catherine Greenhill Mark Jerrum
+	Counting independent sets in graphs with bounded bipartite pathwidth	2018	Martin J.S. Dyer Catherine Greenhill Haiko Müller
+ PDF Chat	Rapid mixing of hypergraph independent sets	2018	Jonathan Hermon Allan Sly Yumeng Zhang
+	Fast convergence of the Glauber dynamics for sampling independent sets	1999	Michael Luby Eric Vigoda
+	Mixing times for exclusion processes on hypergraphs	2016	Stephen B. Connor Richard Pymar
+	Mixing times for exclusion processes on hypergraphs	2016	Stephen B. Connor Richard Pymar
+	Exact and approximate counting of graph objects: independent sets, eulerian tours, and more	2011	Daniel Štefankovič Qi Ge
+	Coupling with the stationary distribution and improved sampling for colorings and independent sets	2005	Tom Hayes Eric Vigoda

Works That Cite This (2)

Action	Title	Year	Authors
+	A survey on the use of Markov chains to randomly sample colorings	2006	Alan Frieze Eric Vigoda
+	Metric Construction, Stopping Times and Path Coupling	2005	Magnus Bordewich Martin Dyer Marek Karpiński

Works Cited by This (16)

Action	Title	Year	Authors
+ PDF Chat	Randomly Coloring Constant Degree Graphs	2004	Martin Dyer Alan Frieze Thomas P. Hayes Eric Vigoda
+	Colouring graphs when the number of colours is nearly the maximum degree	2001	Michael Molloy Bruce Reed
+	Graph orientations with no sink and an approximation for a hard case of #SAT	1997	Russ Bubley Martin Dyer
+	On Markov Chains for Independent Sets	2000	Martin Dyer Catherine Greenhill
+	Very rapidly mixing Markov chains for 2?-colorings and for independent sets in a graph with maximum degree 4	2001	Michael Molloy
+	The complexity of counting graph homomorphisms	2000	Martin Dyer Catherine Greenhill
+	On Approximately Counting Colorings of Small Degree Graphs	1999	Russ Bubley Martin Dyer Catherine Greenhill Mark Jerrum
+	Fast convergence of the Glauber dynamics for sampling independent sets	1999	Michael Luby Eric Vigoda
+	On Counting Independent Sets in Sparse Graphs	2002	Martin Dyer Alan Frieze Mark Jerrum
+	Variable length path coupling	2004	Thomas P. Hayes Eric Vigoda