Survey Propagation as “Probabilistic Token Passing”

Ronghui TU; Yongyi MAO; Jiying ZHAO

doi:10.1093/ietisy/e91-d.2.231

IEICE Transactions on Information and Systems

Online ISSN : 1745-1361
Print ISSN : 0916-8532

Special Section on Foundations of Computer Science

Survey Propagation as “Probabilistic Token Passing”

Ronghui TU, Yongyi MAO, Jiying ZHAO

Author information

Keywords: constraint-satisfaction problem, survey propagation, graph coloring, message-passing

JOURNAL FREE ACCESS

2008 Volume E91.D Issue 2 Pages 231-233

DOI https://doi.org/10.1093/ietisy/e91-d.2.231

Details

Abstract

In this paper, we present a clean and simple formulation of survey propagation (SP) for constraint-satisfaction problems as “probabilistic token passing”. The result shows the importance of extending variable alphabets to their power sets in designing SP algorithms.

Content from these authors

Favorites & Alerts

Corresponding author

Register with J-STAGE for free!