Graph classes and the switch Markov chain for matchings

DOI10.5802/AFST.1469zbMATH Open1337.60171OpenAlexW1752753627WikidataQ59896270 ScholiaQ59896270MaRDI QIDQ5963358FDOQ5963358

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)

Cites Work

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

Cited In (2)

• On the switch Markov chain for perfect matchings
• Counting Perfect Matchings and the Switch Chain

   Recommendations

• On the Switch Markov Chain for Perfect Matchings 👍 👎
• On the switch Markov chain for perfect matchings 👍 👎
• On switching classes of graphs 👍 👎
• Exchangeable pairs, switchings, and random regular graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Half-graphs, other non-stable degree sequences, and the switch Markov chain 👍 👎
• Title not available (Why is that?) 👍 👎
• Random permutation graphs and related Markov chains 👍 👎
• The switch Markov chain for sampling irregular graphs and digraphs 👍 👎

This page was built for publication: Graph classes and the switch Markov chain for matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963358)