ITP OpenIR  > 理论物理所科研产出  > SCI论文
Zhou, HJ; Zhou, HJ (reprint author), Chinese Acad Sci, Key Lab Theoret Phys, Inst Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.
A spin glass approach to the directed feedback vertex set problem
Source PublicationJOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Language英语
KeywordSpin Glasses (Theory) Message-passing Algorithms
AbstractA directed graph (digraph) is formed by vertices and arcs (directed edges) from one vertex to another. A feedback vertex set (FVS) is a set of vertices that contains at least one vertex of every directed cycle in this digraph. The directed feedback vertex set problem aims at constructing a FVS of minimum cardinality. This is a fundamental cycle-constrained hard combinatorial optimization problem with wide practical applications. In this paper we construct a spin glass model for the directed FVS problem by converting the global cycle constraints into local arc constraints, and study this model through the replica-symmetric (RS) mean field theory of statistical physics. We then implement a belief propagation-guided decimation (BPD) algorithm for single digraph instances. The BPD algorithm slightly outperforms the simulated annealing algorithm on large random graph instances. The RS mean field results and algorithmic results can be further improved by working on a more restrictive (and more difficult) spin glass model.
2016
Pages73303
Subject AreaMechanics ; Physics
DOIhttp://dx.doi.org/10.1088/1742-5468/2016/07/073303
Indexed BySCI
Funding OrganizationNational Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02]
Citation statistics
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/21602
Collection理论物理所科研产出_SCI论文
Corresponding AuthorZhou, HJ (reprint author), Chinese Acad Sci, Key Lab Theoret Phys, Inst Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.
Recommended Citation
GB/T 7714
Zhou, HJ,Zhou, HJ . A spin glass approach to the directed feedback vertex set problem[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,2016:73303.
APA Zhou, HJ,&Zhou, HJ .(2016).A spin glass approach to the directed feedback vertex set problem.JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,73303.
MLA Zhou, HJ,et al."A spin glass approach to the directed feedback vertex set problem".JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT (2016):73303.
Files in This Item:
File Name/Size DocType Version Access License
Spin glass approach (1475KB) 开放获取--Application Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhou, HJ]'s Articles
[Zhou, HJ (reprint author), Chinese Acad Sci, Key Lab Theoret Phys, Inst Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhou, HJ]'s Articles
[Zhou, HJ (reprint author), Chinese Acad Sci, Key Lab Theoret Phys, Inst Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhou, HJ]'s Articles
[Zhou, HJ (reprint author), Chinese Acad Sci, Key Lab Theoret Phys, Inst Theoret Phys, Zhong Guan Cun East Rd 55, 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.