ITP OpenIR  > 理论物理所科研产出  > SCI论文
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
Source PublicationPHYSICAL REVIEW E
AbstractCounting 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.
2009
ISSN1539-3755
Volume79Issue:2Pages:-
Subject AreaPhysics
Indexed BySCI
Funding OrganizationNSFC[10774150] ; NSFC[10774150] ; NSFC[10774150] ; NSFC[10774150]
Citation statistics
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/5394
Collection理论物理所科研产出_SCI论文
Corresponding AuthorZhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
Recommended Citation
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):-.
Files in This Item:
File Name/Size DocType Version Access License
Ground-state entropy(91KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhou, Jie]'s Articles
[Zhou, Haijun]'s Articles
[Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhou, Jie]'s Articles
[Zhou, Haijun]'s Articles
[Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhou, Jie]'s Articles
[Zhou, Haijun]'s Articles
[Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China]'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.