西南交通大学学报2012，Vol.47Issue(1)：32-38,62,8.DOI:10.3969/j.issn.0258-2724.2012.01.006
信息传播算法收敛的后门集
Backdoors of Message Propagation Algorithm Convergence
摘要
Abstract
In order to investigate the convergence of the WP ( warning propagation) algorithm, backdoors of the WP algorithm were given. By assigning values to variables in the backdoors, the Boolean formula can be simplified to sub-formula having factor graph with tree structures, and the convergence of the WP algorithm can be guaranteed in the sub-formula. Finally, a randomized algorithm for solving the backdoors was designed and its feasibility was analyzed. The result show that the randomized algorithm is feasible.关键词
信息传递算法/警示传播算法/原理分析/后门集/算法收敛性Key words
message passing algorithm/ warning propagation algorithm/ principle analysis/ backdoors/ convergence of algorithm分类
信息技术与安全科学引用本文复制引用
王晓峰,许道云,秦永彬..信息传播算法收敛的后门集[J].西南交通大学学报,2012,47(1):32-38,62,8.基金项目
国家自然科学基金资助项目(60863005)本文的研究工作得到贵州大学研究生创新基金的资助(校研理工2011033). （60863005）
