ITP OpenIR  > 理论物理所科研产出  > SCI论文
Weigt, Martin; Zhou, Haijun; Weigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy
Message passing for vertex covers
Source PublicationPHYSICAL REVIEW E
KeywordRandom Graphs Satisfiability Problems Cavity Method Frustration Algorithms Transition Dynamics Number Phase Model
AbstractConstructing 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.
2006
ISSN1539-3755
Volume74Issue:4Pages:-
Subject AreaPhysics
Indexed BySCI
Citation statistics
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/5893
Collection理论物理所科研产出_SCI论文
Corresponding AuthorWeigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy
Recommended Citation
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):-.
Files in This Item:
File Name/Size DocType Version Access License
Message passing for (431KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Weigt, Martin]'s Articles
[Zhou, Haijun]'s Articles
[Weigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy]'s Articles
Baidu academic
Similar articles in Baidu academic
[Weigt, Martin]'s Articles
[Zhou, Haijun]'s Articles
[Weigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Weigt, Martin]'s Articles
[Zhou, Haijun]'s Articles
[Weigt, M , Inst Sci Interchange, Viale Settimio Severo 65, I-10133 Turin, Italy]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.