Mixing of Markov chains for independent sets on chordal graphs with bounded separators

DOI10.1007/978-3-030-58150-3_54OpenAlexW3081583587MaRDI QIDQ2019517

Ivona Bezáková, Wenbo Sun

Publication date: 21 April 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-58150-3_54

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Counting in two-spin models on \(d\)-regular graphs
• On the hardness of sampling independent sets beyond the tree threshold
• A note on the Glauber dynamics for sampling independent sets
• A characterisation of rigid circuit graphs
• Counting independent sets in graphs with bounded bipartite pathwidth
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Improved inapproximability results for counting independent sets in the hard-core model
• A Graph Polynomial for Independent Sets of Bipartite Graphs
• Counting independent sets up to the tree threshold
• On Counting Independent Sets in Sparse Graphs
• Approximating the Permanent
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• Fast convergence of the Glauber dynamics for sampling independent sets
• On Markov Chains for Independent Sets
• Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Mixing of Markov chains for independent sets on chordal graphs with bounded separators