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
|
| 刊名 | PHYSICAL REVIEW E
 |
| 出版日期 | 2009 |
| 卷号 | 80期号:2页码:- |
| 关键词 | Satisfiability Problems Glass-transition Bethe Lattices Dynamics Phase |
| ISSN号 | 1539-3755 |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| URL标识 | 查看原文 |
| WOS记录号 | WOS:000269637800032 |
| 公开日期 | 2012-08-02 |
| 源URL | [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):-. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。