Sampling Edge Covers in 3-Regular Graphs

DOI10.1007/978-3-642-03816-7_13MaRDI QIDQ3182920zbMATH OpenOpenAlexFDO

Authors Ivona Bezáková, William A. Rummler

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

cycle decompositionedge coverGlauber dynamicshexagonal latticelattice graphsMarkov chainpath decompositionrapid mixing

Mathematics Subject Classification ID

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

Recommendations

• A simple FPTAS for counting edge covers
• Edge cover time for regular graphs
• Fast convergence of the Glauber dynamics for sampling independent sets
• Short cycle covers of cubic graphs
• The switch Markov chain for sampling irregular graphs (extended abstract)

Cites work

• A note on the Glauber dynamics for sampling independent sets
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Analyzing Glauber dynamics by comparison of Markov chains
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximating the Permanent
• Comparison theorems for reversible Markov chains
• Geometric bounds for eigenvalues of Markov chains
• scientific article; zbMATH DE number 1334601 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Markov chain algorithms for planar lattice structures
• Sampling Regular Graphs and a Peer-to-Peer Network
• The complexity of computing the permanent

Cited in

(5)

• Sampling Eulerian orientations of triangular lattice graphs
• Some applications of Wagner's weighted subgraph counting polynomial
• A simple FPTAS for counting edge covers
• Sampling Multiple Edges Efficiently
• Spectral independence via stability and applications to Holant-type problems

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

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