Graph classes and the switch Markov chain for matchings
From MaRDI portal
Publication:5963358
DOI10.5802/afst.1469zbMath1337.60171WikidataQ59896270 ScholiaQ59896270MaRDI QIDQ5963358
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
60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
05C38: Paths and cycles
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
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