Counting Perfect Matchings and the Switch Chain

DOI10.1137/18M1172910zbMath1432.05053arXiv1705.05790OpenAlexW2963972320WikidataQ127566627 ScholiaQ127566627MaRDI QIDQ5232145

Martin Dyer, Haiko Müller

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.05790

zbMATH Keywords

Markov chainsmatchingsapproximate countinghereditary graph classes

Mathematics Subject Classification ID

Nonparametric statistical resampling methods (62G09) Enumeration in graph theory (05C30) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Geometric bounds on the fastest mixing Markov chain, Efficient generation of random derangements with the expected distribution of cycle lengths, Quasimonotone graphs, The Perfect Matching Reconfiguration Problem

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The strong perfect graph theorem
• Characterizations of strongly chordal graphs
• Characterizing intersection classes of graphs
• Random generation of combinatorial structures from a uniform distribution
• Bipartite permutation graphs
• Complement reducible graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Approximating the permanent of graphs with large factors
• Treewidth. Computations and approximations
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• A simple linear time algorithm for cograph recognition
• Algorithmic graph theory and perfect graphs
• On counting perfect matchings in general graphs
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximating the Permanent
• Undirected connectivity in log-space
• Graph Classes: A Survey
• On the Switch Markov Chain for Perfect Matchings
• Interval bigraphs and circular arc graphs
• Even-hole-free graphs: A survey
• Statistical problems involving permutations with restricted positions
• Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
• Quasimonotone graphs
• Graph classes and the switch Markov chain for matchings