On Markov Chains for Independent Sets

DOI10.1006/jagm.1999.1071zbMath0961.05063OpenAlexW1986979529WikidataQ56324027 ScholiaQ56324027MaRDI QIDQ4953244

Catherine Greenhill, Martin Dyer

Publication date: 4 October 2000

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/2ccd2afa07ba1194e962daa653bb17423ef75738

zbMATH Keywords

probability distributionhypergraphsindependent setsMarkov chain Monte Carlo methods

Mathematics Subject Classification ID

Hypergraphs (05C65) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (33)

Spatial mixing and the connective constant: optimal bounds ⋮ Perfect sampling using bounding chains. ⋮ A probabilistic approach to convex \((\phi)\)-entropy decay for Markov chains ⋮ Unnamed Item ⋮ A Graph Polynomial for Independent Sets of Bipartite Graphs ⋮ On Sampling Simple Paths in Planar Graphs According to Their Lengths ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ Fast algorithms at low temperatures via Markov chains† ⋮ Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials ⋮ Unnamed Item ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ Spatial birth-death swap chains ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ Path coupling without contraction ⋮ Approximation via Correlation Decay When Strong Spatial Mixing Fails ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz ⋮ A path integral method for data assimilation ⋮ Approximately counting paths and cycles in a graph ⋮ Mixing of Markov chains for independent sets on chordal graphs with bounded separators ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Glauber dynamics on trees and hyperbolic graphs ⋮ On systematic scan for sampling H-colorings of the path ⋮ Rapid mixing of Gibbs sampling on graphs that are sparse on average ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ Sampling independent sets in the discrete torus ⋮ Gibbs rapidly samples colorings of \(G(n, d/n)\) ⋮ On the hardness of sampling independent sets beyond the tree threshold ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ Faster random generation of linear extensions ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Dynamic Sampling from Graphical Models ⋮ Polymer dynamics via cliques: new conditions for approximations

This page was built for publication: On Markov Chains for Independent Sets