Sampling Edge Covers in 3-Regular Graphs

DOI10.1007/978-3-642-03816-7_13zbMath1250.05085OpenAlexW1485288837MaRDI 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

zbMATH Keywords

Markov chainGlauber dynamicsedge coverpath decompositioncycle decompositionlattice graphshexagonal latticerapid mixing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Some applications of Wagner's weighted subgraph counting polynomial

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

This page was built for publication: Sampling Edge Covers in 3-Regular Graphs