Backdoors of Message Propagation Algorithm Convergence

　　[1]　CHEESEMAN P, KANEFSKY B,TAYLOR W M. Where the really hard problems are[C]∥Proceedings of the 12th International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann,1991: 331-337. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [2]　FRIEZE A M, MOLLOY M. The satisfiability threshold for randomly generated binary constraint satisfaction problems[J]. Proceedings of Random, 2006, 28(3): 323-339. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [3]　ZHANG W. Phase transitions and backbones of 3-SAT and maximum 3-SAT[C]∥Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming. London: Springer, 2001: 153-167. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [4]　YANNAKAKIS M. Node and edge deletion NP-complete problems[C]∥Proceedings of the 10th Annual ACM Symposium on Theory of Computing. New York: ACM, 1978: 253-264. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [5]　DUBOIS O, DEQUEN G. A backbone search heuristic for efficient solving of hard 3-SAT formulae[C]∥Proceedings of the 17th International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2001: 248-253. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [6]　SLANEY J, WALSH T. Backbones in optimization and approximation[C]∥Proceedings of the 17th Interna-tional Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2001: 254-259. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [7]　KILBY P, SLANEY J, THIEBAUX S, et al. Backbones and backdoors in satisfiability[C]∥Proceedings of the 20th National Conference on Artificial Intelligence. Pittsburgh: AAAI, 2005: 1368-1373. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [8]　WILLIAMS R, GOMES C P, SELMAN B. Backdoors to typical case complexity[C]∥Proceedings of the 18th International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2003: 1173-1178. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [9]　NISHIMURA N, RAGDE P, SZEIDER S. Detecting backdoor sets with respect to horn and binary clauses[C]∥Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing. Vancouver: Elsevier, 2004: 96-103. [10]　SAMER M, SZERDER S. Backdoor trees[C]∥Proceedings of the 23rd National Conference on Artificial Intelligence. Chicago: AAAI, 2008: 363-368. 　　　　 [11]　RUAN Y, KAUTZ H, HORVITZ E. The backdoor key: a path to understanding problem hardness[C]∥Proceedings of the 19th National Conference on Artificial Intelligence. [S.l.]: AAAI, 2004: 124-130. 　　　 [12]　SELMAN B, KAUTZ H, COHEN B. Noise strategies for improving local search[C]∥Proceedings of the 12th National Conference on Artificial Intelligence. Seattle: AAAI, 1994: 337-343. 　　　　 [13]　MCALLESTER D, SELMAN B, KAUTZ H. Evidence for invariants in local search[C]∥Proceedings of the 14th National Conference on Artificial Intelligence and 9th Conference on Innovative Applications of Artificial Intelligence. [S.l.]: AAAI, 1997: 321-326. 　　　　 [14]　MOSKEWICZ M W, MADIGAN C F, ZHAO Y. Chaff: Engineering an efficient SAT solver[C]∥Proceedings of the 38th Annual Design Automation Conference. New York: ACM, 2001: 530-535. 　　　　 [15]　BRAUNSTEIN A, MEZARD M, ZECCHINA R. Survey propagation: an algorithm for satisfiability[J]. Random Structures and Algorithms, 2005, 27(2): 201-226. 　　 [16]　MANEVA E, MOSSEL E, WAINWRIGHT M. A new look at survey propagation and its generalizations[J]. Journal of the ACM, 2007, 54(4): 1089-1098. 　　　　 [17]　秦永彬,许道云. 警示传播算法的原理分析及算法改进[J]. 计算机工程与应用,2010,46(19): 1-6. 　　　　QIN Yongbin, XU Daoyun. Analysis and improvement of warning propagation algorithm[J]. Computer Engineering and Applications, 2010, 46(19): 1-6. 　　　　 [18]　邵明,李光辉,李晓维. 求解可满足问题的调查传播算法以及步长的影响规律[J]. 计算机学报,2005,28(5): 849-855. 　　　　SHAO Ming, LI Guanghui, LI Xiaowei. Survey propagation algorithm for SAT and its performance dominated by step length[J]. Chinese Journal of Computers, 2005, 28(5): 849-855. 　　　　 [19]　李韶华,张健. Survey propagation:一种求解SAT的高效算法[J]. 计算机科学,2005,32(1): 132-137. 　　　　LI Shaohua, ZHANG Jian. Survey propagation: an effective algorithm for solving SAT[J. Journal of Computer Sciense, 2005, 32(1): 132-137. 　　　　 [20]　KSCHISCHANG F, FREY B, LOELIGER H. Factor graph and the sum-product algorithm[J]. Information Theory, 2001, 47（1）: 498-519. 　　　　 [21]　FEIGE U, MOSSEL E, VILENCHIK D. Complete convergence of message passing algorithms for some satisfiability problems[J]. Lecture Notes in Computer Science, 2006, 4110（1）: 339-350. 　　　　 [22]　王晓峰,许道云. 求解公式关键文字集的信息传播算法[J]. 山东大学学报:工学版,2011,41(3): 1-6. 　　　　WANG Xiaofeng, XU Daoyun. A message propagation algorithm computing set of key literals of a formula[J]. Journal of Shandong University: Engineering Science, 2011, 41(3): 1-6.