Message passing for vertex covers
文献类型：期刊论文
| 作者 | Weigt, Martin; Zhou, Haijun ; Weigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy
|
| 刊名 | PHYSICAL REVIEW E
 |
| 出版日期 | 2006 |
| 卷号 | 74期号:4页码:- |
| 关键词 | Random Graphs Satisfiability Problems Cavity Method Frustration Algorithms Transition Dynamics Number Phase Model |
| ISSN号 | 1539-3755 |
| 英文摘要 | Constructing a minimal vertex cover of a graph can be seen as a prototype for a combinatorial optimization problem under hard constraints. In this paper, we develop and analyze message-passing techniques, namely, warning and survey propagation, which serve as efficient heuristic algorithms for solving these computational hard problems. We show also, how previously obtained results on the typical-case behavior of vertex covers of random graphs can be recovered starting from the message-passing equations, and how they can be extended. |
| 学科主题 | Physics |
| URL标识 | 查看原文 |
| WOS记录号 | WOS:000241723000019 |
| 公开日期 | 2012-08-02 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/5893]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 通讯作者 | Weigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy |
| 推荐引用方式 GB/T 7714 | Weigt, Martin,Zhou, Haijun,Weigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy. Message passing for vertex covers[J]. PHYSICAL REVIEW E,2006,74(4):-. |
| APA | Weigt, Martin,Zhou, Haijun,&Weigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy.(2006).Message passing for vertex covers.PHYSICAL REVIEW E,74(4),-. |
| MLA | Weigt, Martin,et al."Message passing for vertex covers".PHYSICAL REVIEW E 74.4(2006):-. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。