Convergence analysis of belief propagation algorithm for satisfiability problem

DOI10.13328/J.CNKI.JOS.005844MaRDI QIDQ3381512zbMATH OpenFDO

Authors Deren Yang, Jiulei Jiang, Qiang Li, Xiao-Feng Wang, Daoyun Xu, Xin Xin Liu

Publication date 29 September 2021

Full work available at URL https://doi.org/10.13328/J.CNKI.JOS.005844

zbMATH Keywords

belief propagation algorithmconvergencefactor graphsatisfiability problem

Mathematics Subject Classification ID

Probabilistic graphical models (62H22) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Convergence of the belief propagation algorithm for RB model instances
• Theory and Applications of Satisfiability Testing
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• Complete convergence of message passing algorithms for some satisfiability problems
• Convergence and correctness of belief propagation for the Chinese postman problem

Cited in

(4)

• scientific article; zbMATH DE number 5885078 (Why is no real title available?)
• An analysis of belief propagation on the turbo decoding graph with Gaussian densities
• Convergence of the belief propagation algorithm for RB model instances
• Convergence and Correctness of Max-Product Belief Propagation for Linear Programming

This page was built for publication: Convergence analysis of belief propagation algorithm for satisfiability problem

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