Sampling Edge Covers in 3-Regular Graphs
From MaRDI portal
Publication:3182920
DOI10.1007/978-3-642-03816-7_13zbMath1250.05085MaRDI QIDQ3182920
William A. Rummler, Ivona Bezáková
Publication date: 16 October 2009
Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_13
Markov chain; Glauber dynamics; edge cover; path decomposition; cycle decomposition; lattice graphs; hexagonal lattice; rapid mixing
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Cites Work
- Unnamed Item
- The complexity of computing the permanent
- Geometric bounds for eigenvalues of Markov chains
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Comparison theorems for reversible Markov chains
- A note on the Glauber dynamics for sampling independent sets
- Analyzing Glauber dynamics by comparison of Markov chains
- Markov Chain Algorithms for Planar Lattice Structures
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Approximating the Permanent
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Sampling Regular Graphs and a Peer-to-Peer Network