ISBN: 978-981-11-0008-6 DOI: 10.18178/wcse.2016.06.081
Probability Conditions for Convergence of the Warning Propagation Algorithm
Abstract— Message propagation algorithms are very effective in finding satisfying assignments for random
SAT instances, and hard region become narrower. However, message propagation algorithms do not always
converge for graphs with cycles. Unfortunately, rigorous theory proof of this phenomenon is still lacking.
Warning Propagation algorithm is the most basic message propagation algorithm, we analyses convergence
of the warning propagation algorithm, and gives the conditions for convergence.
Index Terms— warning propagation algorithm, convergence, satisfiability problems
Wang Xiao-feng, Ding Hong-sheng, Yu Qian-cheng, Tian Jin-qin
Department of Computer Science, Beifang Minzu University, CHINA
Cite: Wang Xiao-feng, Ding Hong-sheng, Yu Qian-cheng, Tian Jin-qin, "Probability Conditions for Convergence of the Warning Propagation Algorithm," Proceedings of 2016 6th International Workshop on Computer Science and Engineering, pp. 481-488, Tokyo, 17-19 June, 2016.