On the switch Markov chain for perfect matchings

DOI10.1145/2822322MaRDI QIDQ4640285zbMATH OpenOpenAlexWikidataFDO

Authors Martin Dyer, Haiko Müller, Mark Jerrum

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL http://eprints.whiterose.ac.uk/111478/1/monotone.pdf

zbMATH Keywords

bipartite graphscounting problemshereditary graph classesperfect matchingpermanent

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20)

Recommendations

• On the switch Markov chain for perfect matchings
• Graph classes and the switch Markov chain for matchings
• Counting perfect matchings and the switch chain
• The mixing time of switch Markov chains: a unified approach
• Rapid mixing of the switch Markov chain for strongly stable degree sequences

Cited in

(23)

• Sampling weighted perfect matchings on the square-octagon lattice
• Random walks on trees and matchings
• Permanental generating functions and sequential importance sampling
• Zero-freeness and approximation of real Boolean Holant problems
• Parikh word representability of bipartite permutation graphs
• Efficient generation of random derangements with the expected distribution of cycle lengths
• Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
• Efficient, local and symmetric Markov chains that generate one-factorizations
• The mixing time of switch Markov chains: a unified approach
• Complexity of Hamiltonian cycle reconfiguration
• Sequential importance sampling for estimating the number of perfect matchings in bipartite graphs: an ongoing conversation with Laci
• The Effect of Boundary Conditions on Mixing Rates of Markov Chains
• On the switch Markov chain for perfect matchings
• Rapid mixing of the switch Markov chain for 2-class joint degree matrices
• The Perfect Matching Reconfiguration Problem
• Sampling weighted perfect matchings on the square-octagon lattice
• Counting perfect matchings and the switch chain
• Quasimonotone graphs
• Quasimonotone graphs
• Graph classes and the switch Markov chain for matchings
• Counting independent sets in graphs with bounded bipartite pathwidth
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• Critically fixed Thurston maps: classification, recognition, and twisting

This page was built for publication: On the switch Markov chain for perfect matchings

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