Sufficient Conditions for Convergence of the Warning Propagation Algorithm
Author:
Affiliation:

Clc Number:

Fund Project:

National Natural Science Foundation of China (61462001, 61262006, 61402017); Natural Science Foundation of Ningxia Province of China (NZ14108); Natural Science Foundation of Beifang Unversity of Nationalities (2014XYZ03, 2014XBZ04); Key Subject Foundation of Computer application technology of Ningxia

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Message propagation algorithms are very effective in finding satisfying assignments for 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 (WP) algorithm is the most basic message propagation algorithm, we have derived the sufficient conditions for convergence of the warning propagation algorithm. Lastly, experimental results show that such conditions for convergence of WP are very effective in different group data from random satisfiable 3-SAT instances.

    Reference
    Related
    Cited by
Get Citation

王晓峰,许道云.警示传播算法收敛的充分条件.软件学报,2016,27(12):3003-3013

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 28,2014
  • Revised:July 27,2015
  • Adopted:
  • Online: December 08,2015
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063