Counting Perfect Matchings and the Switch Chain
From MaRDI portal
Publication:5232145
DOI10.1137/18M1172910zbMath1432.05053arXiv1705.05790WikidataQ127566627 ScholiaQ127566627MaRDI QIDQ5232145
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
62G09: Nonparametric statistical resampling methods
05C30: Enumeration in graph theory
60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
The Perfect Matching Reconfiguration Problem, Quasimonotone graphs, Efficient generation of random derangements with the expected distribution of cycle lengths
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
