Ground-state entropy of the random vertex-cover problem | |
Zhou, Jie; Zhou, Haijun![]() | |
刊名 | PHYSICAL REVIEW E
![]() |
2009 | |
卷号 | 79期号:2页码:- |
ISSN号 | 1539-3755 |
英文摘要 | Counting the number of ground states for a spin-glass or nondeterministic polynomial-complete combinatorial optimization problem is even more difficult than the already hard task of finding a single ground state. In this paper the entropy of minimum vertex covers of random graphs is estimated through a set of iterative equations based on the cavity method of statistical mechanics. During the iteration both the cavity entropy contributions and cavity magnetizations for each vertex are updated. This approach overcomes the difficulty of iterative divergence encountered in the zero-temperature first-step replica-symmetry-breaking (1RSB) spin-glass theory. It is still applicable when the 1RSB mean-field theory is no longer stable. The method can be extended to compute the entropies of ground states and metastable minimal-energy states for other random-graph spin-glass systems. |
学科主题 | Physics |
URL标识 | 查看原文 |
WOS记录号 | WOS:000263807300003 |
公开日期 | 2012-08-02 |
内容类型 | 期刊论文 |
源URL | [http://ir.itp.ac.cn/handle/311006/5394] ![]() |
专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
通讯作者 | Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China |
推荐引用方式 GB/T 7714 | Zhou, Jie,Zhou, Haijun,Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China. Ground-state entropy of the random vertex-cover problem[J]. PHYSICAL REVIEW E,2009,79(2):-. |
APA | Zhou, Jie,Zhou, Haijun,&Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China.(2009).Ground-state entropy of the random vertex-cover problem.PHYSICAL REVIEW E,79(2),-. |
MLA | Zhou, Jie,et al."Ground-state entropy of the random vertex-cover problem".PHYSICAL REVIEW E 79.2(2009):-. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论