ITP OpenIR  > 理论物理所SCI论文
Solving the undirected feedback vertex set problem by local search
Qin, SM; Zhou, HJ; Qin, SM (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
2014
发表期刊EUROPEAN PHYSICAL JOURNAL B
ISSN1434-6028
卷号87期号:11页码:273
摘要An undirected graph consists of a set of vertices and a set of undirected edges between vertices. Such a graph may contain an abundant number of cycles, in which case a feedback vertex set (FVS) is a set of vertices intersecting with each of these cycles. Constructing a FVS of cardinality approaching the global minimum value is an optimization problem in the nondeterministic polynomial-complete complexity class, and therefore it might be extremely difficult for some large graph instances. In this paper we develop a simulated annealing local search algorithm for the undirected FVS problem by adapting the heuristic procedure of Galinier et al. [P. Galinier, E. Lemamou, M.W. Bouzidi, J. Heuristics 19, 797 (2013)], which worked for the directed FVS problem. By defining an order for the vertices outside the FVS, we replace the global cycle constraints by a set of local vertex constraints on this order. Under these local constraints the cardinality of the focal FVS is then gradually reduced by the simulated annealing dynamical process. We test this heuristic algorithm on large instances of Erdos-Renyi random graph and regular random graph, and find that this algorithm is comparable in performance to the belief propagation-guided decimation algorithm.
部门归属[Qin, Shao-Meng
关键词Graphs
学科领域Physics
资助者National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526]
DOI10.1140/epjb/e2014-50289-7
URL查看原文
收录类别SCI
语种英语
资助者National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526]
WOS记录号WOS:000354372000003
引用统计
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/15568
专题理论物理所SCI论文
通讯作者Qin, SM (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
推荐引用方式
GB/T 7714
Qin, SM,Zhou, HJ,Qin, SM . Solving the undirected feedback vertex set problem by local search[J]. EUROPEAN PHYSICAL JOURNAL B,2014,87(11):273.
APA Qin, SM,Zhou, HJ,&Qin, SM .(2014).Solving the undirected feedback vertex set problem by local search.EUROPEAN PHYSICAL JOURNAL B,87(11),273.
MLA Qin, SM,et al."Solving the undirected feedback vertex set problem by local search".EUROPEAN PHYSICAL JOURNAL B 87.11(2014):273.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Solving the undirect(360KB) 开放获取CC BY-NC-SA请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Qin, SM]的文章
[Zhou, HJ]的文章
[Qin, SM (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]的文章
百度学术
百度学术中相似的文章
[Qin, SM]的文章
[Zhou, HJ]的文章
[Qin, SM (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]的文章
必应学术
必应学术中相似的文章
[Qin, SM]的文章
[Zhou, HJ]的文章
[Qin, SM (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。