On the switch Markov chain for perfect matchings

DOI10.1145/2822322zbMATH Open1426.60097OpenAlexW1488013613WikidataQ59888598 ScholiaQ59888598MaRDI QIDQ4640285FDOQ4640285

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

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

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)

Cited In (22)

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