Graph classes and the switch Markov chain for matchings

DOI10.5802/afst.1469zbMath1337.60171OpenAlexW1752753627WikidataQ59896270 ScholiaQ59896270MaRDI QIDQ5963358

Haiko Müller, Martin Dyer

Publication date: 19 February 2016

Published in: Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/67ce85834ec322daca414002f8d5d42fa862c945

zbMATH Keywords

graphsmatchingsswitch Markov chain

Mathematics Subject Classification ID

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

Related Items

Counting Perfect Matchings and the Switch Chain

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• On minimizing width in linear layouts
• Recognizing graphs without asteroidal triples
• Graph minors. I. Excluding a forest
• Random generation of combinatorial structures from a uniform distribution
• Bipartite permutation graphs
• The vertex separation number of a graph equals its path-width
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The vertex separation and search number of a graph
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• A random walk on the rook placements on a Ferrers board
• A structure theorem for the consecutive 1's property
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximating the Permanent
• Pathwidth of outerplanar graphs
• Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
• Approximate counting by dynamic programming
• Doubly Lexical Orderings of Matrices
• Computing the Minimum Fill-In is NP-Complete
• Graph Classes: A Survey
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Handbook of Graph Theory
• Nonredundant 1’s in $\Gamma $-Free Matrices
• Statistical problems involving permutations with restricted positions
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
• Maximum matching in a convex bipartite graph
• Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic