Knowledge Management System of Institute of Theoretical Physics, CAS
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. | |
Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs | |
发表期刊 | JOURNAL OF STATISTICAL PHYSICS |
语种 | 英语 |
关键词 | Feedback Arc Set Directed Cycle Replica-symmetric Belief Propagation Segmentation Mean Field Theory Algorithm |
摘要 | 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. |
2017 | |
卷号 | 169期号:1页码:187-202 |
学科领域 | Physics |
DOI | http://dx.doi.org/10.1007/s10955-017-1860-5 |
项目资助者 | 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] |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.itp.ac.cn/handle/311006/21962 |
专题 | SCI期刊论文 |
通讯作者 | 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) | 开放获取 | -- | 请求全文 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论