Graph classes and the switch Markov chain for matchings

DOI10.5802/AFST.1469MaRDI QIDQ5963358zbMATH OpenOpenAlexWikidataFDO

Authors Martin Dyer, Haiko Müller

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

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

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
• scientific article; zbMATH DE number 6450685
• Half-graphs, other non-stable degree sequences, and the switch Markov chain
• scientific article; zbMATH DE number 4057569
• Random permutation graphs and related Markov chains
• The switch Markov chain for sampling irregular graphs and digraphs

Cites work

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

Cited in

(5)

• Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
• On the switch Markov chain for perfect matchings
• On the switch Markov chain for perfect matchings
• Counting perfect matchings and the switch chain
• Quasimonotone graphs

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)