ITP OpenIR  > 理论物理所2017年知识产出
Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs
Xu, YZ; Zhou, HJ; Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.; Zhou, HJ (reprint author), Univ Chinese Acad Sci, Sch Phys Sci, Beijing 100049, Peoples R China.
2017
发表期刊JOURNAL OF STATISTICAL PHYSICS
卷号169期号:1页码:187-202
文章类型Article
摘要The minimum feedback arc set problem asks to delete a minimum number of arcs (directed edges) from a digraph (directed graph) to make it free of any directed cycles. In this work we approach this fundamental cycle-constrained optimization problem by considering a generalized task of dividing the digraph into D layers of equal size. We solve the D-segmentation problem by the replica-symmetric mean field theory and belief-propagation heuristic algorithms. The minimum feedback arc density of a given random digraph ensemble is then obtained by extrapolating the theoretical results to the limit of large D. A divide-and-conquer algorithm (nested-BPR) is devised to solve the minimum feedback arc set problem with very good performance and high efficiency.
关键词Feedback Arc Set Directed Cycle Replica-symmetric Belief Propagation Segmentation Mean Field Theory Algorithm
学科领域Physics
资助者National Natural Science Foundation of China [11121403, 11647601] ; National Natural Science Foundation of China [11121403, 11647601] ; National Natural Science Foundation of China [11121403, 11647601] ; National Natural Science Foundation of China [11121403, 11647601]
DOIhttp://dx.doi.org/10.1007/s10955-017-1860-5
关键词[WOS]COMBINATORIAL OPTIMIZATION ; STATISTICAL-MECHANICS ; REGULAR GRAPHS ; SPIN-GLASS ; NETWORKS
语种英语
资助者National Natural Science Foundation of China [11121403, 11647601] ; National Natural Science Foundation of China [11121403, 11647601] ; National Natural Science Foundation of China [11121403, 11647601] ; National Natural Science Foundation of China [11121403, 11647601]
WOS类目Physics, Mathematical
引用统计
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/21962
专题理论物理所2017年知识产出
通讯作者Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.; Zhou, HJ (reprint author), Univ Chinese Acad Sci, Sch Phys Sci, Beijing 100049, Peoples R China.
推荐引用方式
GB/T 7714
Xu, YZ,Zhou, HJ,Zhou, HJ ,et al. Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs[J]. JOURNAL OF STATISTICAL PHYSICS,2017,169(1):187-202.
APA Xu, YZ,Zhou, HJ,Zhou, HJ ,&Zhou, HJ .(2017).Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs.JOURNAL OF STATISTICAL PHYSICS,169(1),187-202.
MLA Xu, YZ,et al."Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs".JOURNAL OF STATISTICAL PHYSICS 169.1(2017):187-202.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Optimal Segmentation(650KB) 开放获取--请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Xu, YZ]的文章
[Zhou, HJ]的文章
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.]的文章
百度学术
百度学术中相似的文章
[Xu, YZ]的文章
[Zhou, HJ]的文章
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.]的文章
必应学术
必应学术中相似的文章
[Xu, YZ]的文章
[Zhou, HJ]的文章
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

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