Message passing for vertex covers

CORC > 理论物理研究所 > 中国科学院理论物理研究所 > 理论物理所科研产出 > 理论物理所1978-2010年知识产出

	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):-.