中国科学院理论物理研究所机构知识库
Advanced  
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
刊名: PHYSICAL REVIEW E
出版日期: 2009
卷号: 80, 期号:2, 页码:-
关键词: SATISFIABILITY PROBLEMS ;  GLASS-TRANSITION ;  BETHE LATTICES ;  DYNAMICS ;  PHASE
学科分类: Physics
通讯作者: Zhang, P , Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
部门归属: [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
英文摘要: 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.
资助者: National Science Foundation of China[10774150]; 973-Program of China[2007CB935903]
收录类别: SCI
原文出处: 查看原文
WOS记录号: WOS:000269637800032
Citation statistics: 
内容类型: 期刊论文
URI标识: http://ir.itp.ac.cn/handle/311006/5271
Appears in Collections:理论物理所1978-2010年知识产出_期刊论文

Files in This Item: Download All
File Name/ File Size Content Type Version Access License
Stability analysis on the finite-temperature replica-symmetric and first-step.pdf(532KB)----开放获取View Download

Recommended Citation:
Zhang, Pan,Zeng, Ying,Zhou, Haijun. 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):-.
Service
 Recommend this item
 Sava as my favorate item
 Show this item's statistics
 Export Endnote File
Google Scholar
 Similar articles in Google Scholar
 [Zhang, Pan]'s Articles
 [Zeng, Ying]'s Articles
 [Zhou, Haijun]'s Articles
CSDL cross search
 Similar articles in CSDL Cross Search
 [Zhang, Pan]‘s Articles
 [Zeng, Ying]‘s Articles
 [Zhou, Haijun]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
  Add to CiteULike  Add to Connotea  Add to Del.icio.us  Add to Digg  Add to Reddit 
文件名: Stability analysis on the finite-temperature replica-symmetric and first-step.pdf
格式: Adobe PDF
此文件暂不支持浏览
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院理论物理研究所 - Feedback
Powered by CSpace