On the Switch Markov Chain for Perfect Matchings
From MaRDI portal
Publication:4640285
DOI10.1145/2822322zbMath1426.60097OpenAlexW1488013613WikidataQ59888598 ScholiaQ59888598MaRDI QIDQ4640285
Martin Dyer, Haiko Müller, Mark R. 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
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20)
Related Items
Complexity of Hamiltonian cycle reconfiguration, 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, 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, Permanental generating functions and sequential importance sampling, Counting independent sets in graphs with bounded bipartite pathwidth, Quasimonotone graphs, The Perfect Matching Reconfiguration Problem, Counting Perfect Matchings and the Switch Chain, Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices
