Mixing times of Markov chains of 2-orientations

DOI10.1007/978-3-319-30139-6_10MaRDI QIDQ2803817zbMATH OpenOpenAlexFDO

Authors Stefan Felsner, Daniel Heldt

Publication date 3 May 2016

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-30139-6_10

Mathematics Subject Classification ID

Discrete-time Markov processes on general state spaces (60J05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Mixing times of Markov chains on degree constrained orientations of planar graphs
• Mixing times of Markov chains on 3-orientations of planar triangulations
• scientific article; zbMATH DE number 2127753
• Sampling and counting 3-orientations of planar triangulations
• Sampling Eulerian orientations of triangular lattice graphs

Cites work

• scientific article; zbMATH DE number 1261817 (Why is no real title available?)
• A more rapidly mixing Markov chain for graph colorings
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Analyzing Glauber dynamics by comparison of Markov chains
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Bijections for Baxter families and related objects
• Binary labelings for plane quadrangulations and their relatives
• Comparison theorems for reversible Markov chains
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Generating random elements of finite distributive lattices
• Lattice structures from planar graphs
• Markov chain algorithms for Eulerian orientations and 3-colourings of 2-dimensional Cartesian grids
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing times of Markov chains on 3-orientations of planar triangulations
• Mixing times of Markov chains on degree constrained orientations of planar graphs
• On the number of planar orientations with prescribed degrees
• On topological aspects of orientations
• Sampling Eulerian orientations of triangular lattice graphs
• ULD-lattices and \(\Delta \)-bonds

Cited in

(4)

• Mixing times of Markov chains on degree constrained orientations of planar graphs
• A polynomial upper bound for the mixing time of edge rotations on planar maps
• Mixing times of Markov chains on 3-orientations of planar triangulations
• On the mixing time of the face flip- and up/down Markov chain for some families of graphs

This page was built for publication: Mixing times of Markov chains of 2-orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2803817)