On Markov Chains for Independent Sets
From MaRDI portal
Publication:4953244
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
Hypergraphs (05C65) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
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
