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

perfect matchingbipartite graphspermanentcounting problemshereditary graph classes

Mathematics Subject Classification ID

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

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

(22)

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

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)