ITP OpenIR  > SCI期刊论文
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
Source PublicationJOURNAL OF STATISTICAL PHYSICS
Language英语
KeywordFeedback Arc Set Directed Cycle Replica-symmetric Belief Propagation Segmentation Mean Field Theory Algorithm
AbstractThe 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
Volume169Issue:1Pages:187-202
Subject AreaPhysics
DOIhttp://dx.doi.org/10.1007/s10955-017-1860-5
Funding OrganizationNational 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]
Citation statistics
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/21962
CollectionSCI期刊论文
Corresponding AuthorZhou, 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.
Recommended Citation
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.
Files in This Item:
File Name/Size DocType Version Access License
Optimal Segmentation(650KB) 开放获取--Application Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Xu, YZ]'s Articles
[Zhou, HJ]'s Articles
[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.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Xu, YZ]'s Articles
[Zhou, HJ]'s Articles
[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.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Xu, YZ]'s Articles
[Zhou, HJ]'s Articles
[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.]'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.