ITP OpenIR  > 理论物理所科研产出  > SCI论文
Zhang, Pan; Zeng, Ying; Zhou, Haijun; Zhang, P , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
Source PublicationPHYSICAL REVIEW E
KeywordSatisfiability Problems Glass-transition Bethe Lattices Dynamics Phase
AbstractThe vertex cover problem is a prototypical hard combinatorial optimization problem. It was studied in recent years by physicists using the cavity method of statistical mechanics. In this paper, the stability of the finite-temperature replica-symmetric (RS) and the first-step replica-symmetry-broken (1RSB) cavity solutions of the vertex cover problem on random regular graphs of finite vertex degree K are analyzed by population dynamics simulations. We found that (1) the lowest temperature for the RS solution to be stable, T(RS)(K), is not a monotonic function of K; (2) at relatively large connectivity K and temperature T slightly below the dynamic transition temperature T(d)(K), the 1RSB solutions with small but non-negative complexity values are stable, and (3) the dynamical transition temperature T(d) and Kauzmann temperature T(K) is equal to each other. Similar results are obtained on random Poissonian graphs.
2009
ISSN1539-3755
Volume80Issue:2Pages:-
Subject AreaPhysics
Indexed BySCI
Funding OrganizationNational Science Foundation of China[10774150]; 973-Program of China[2007CB935903] ; National Science Foundation of China[10774150]; 973-Program of China[2007CB935903] ; National Science Foundation of China[10774150]; 973-Program of China[2007CB935903] ; National Science Foundation of China[10774150]; 973-Program of China[2007CB935903]
Citation statistics
Cited Times:14[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/5271
Collection理论物理所科研产出_SCI论文
Corresponding AuthorZhang, P , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
Recommended Citation
GB/T 7714
Zhang, Pan,Zeng, Ying,Zhou, Haijun,et al. Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem[J]. PHYSICAL REVIEW E,2009,80(2):-.
APA Zhang, Pan,Zeng, Ying,Zhou, Haijun,&Zhang, P , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China.(2009).Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem.PHYSICAL REVIEW E,80(2),-.
MLA Zhang, Pan,et al."Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem".PHYSICAL REVIEW E 80.2(2009):-.
Files in This Item:
File Name/Size DocType Version Access License
Stability analysis o(532KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhang, Pan]'s Articles
[Zeng, Ying]'s Articles
[Zhou, Haijun]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhang, Pan]'s Articles
[Zeng, Ying]'s Articles
[Zhou, Haijun]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhang, Pan]'s Articles
[Zeng, Ying]'s Articles
[Zhou, Haijun]'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.