Counting Independent Sets Using the Bethe Approximation

DOI10.1137/090767145zbMath1225.68131OpenAlexW2908188374MaRDI QIDQ3094955

Jinwoo Shin, Devavrat Shah, David Gamarnik, Misha Chertkov, Venkat Chandrasekaran

Publication date: 27 October 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090767145

zbMATH Keywords

independent setbelief propagationBethe free energyloop series

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (5)

Limits of discrete distributions and Gibbs measures on random graphs ⋮ Convergence and Correctness of Max-Product Belief Propagation for Linear Programming ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Gauges, loops, and polynomials for partition functions of graphical models

This page was built for publication: Counting Independent Sets Using the Bethe Approximation