ITP OpenIR  > 理论物理所1978-2010年知识产出
Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
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
发表期刊PHYSICAL REVIEW E
ISSN1539-3755
卷号80期号:2页码:-
摘要The 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.
部门归属[Zhang, P; Zeng, Y; Zhou, HJ] Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China; [Zhang, P] Lanzhou Univ, Inst Theoret Phys, Lanzhou 730000, Peoples R China; [Zhou, HJ] Chinese Acad Sci, Inst Theoret Phys, Kavli Inst Theoret Phys China, Beijing 100190, Peoples R China
关键词Satisfiability Problems Glass-transition Bethe Lattices Dynamics Phase
学科领域Physics
资助者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] ; National Science Foundation of China[10774150]; 973-Program of China[2007CB935903]
URL查看原文
收录类别SCI
资助者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] ; National Science Foundation of China[10774150]; 973-Program of China[2007CB935903]
WOS记录号WOS:000269637800032
引用统计
被引频次:12[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/5271
专题理论物理所1978-2010年知识产出
通讯作者Zhang, P , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
推荐引用方式
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):-.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Stability analysis o(532KB) 开放获取使用许可请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Zhang, Pan]的文章
[Zeng, Ying]的文章
[Zhou, Haijun]的文章
百度学术
百度学术中相似的文章
[Zhang, Pan]的文章
[Zeng, Ying]的文章
[Zhou, Haijun]的文章
必应学术
必应学术中相似的文章
[Zhang, Pan]的文章
[Zeng, Ying]的文章
[Zhou, Haijun]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。