Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs
文献类型：期刊论文
| 作者 | 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), Univ Chinese Acad Sci, Sch Phys Sci, Beijing 100049, Peoples R China.
|
| 刊名 | JOURNAL OF STATISTICAL PHYSICS
 |
| 出版日期 | 2017 |
| 卷号 | 169期号:1页码:187-202 |
| 关键词 | Feedback Arc Set Directed Cycle Replica-symmetric Belief Propagation Segmentation Mean Field Theory Algorithm |
| DOI | http://dx.doi.org/10.1007/s10955-017-1860-5 |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| 语种 | 英语 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/21962]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 通讯作者 | 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 | Zhou, HJ ,Xu, YZ,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 | Zhou, HJ ,Xu, YZ,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 | Zhou, HJ ,et al."Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs".JOURNAL OF STATISTICAL PHYSICS 169.1(2017):187-202. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。