ITP OpenIR  > SCI期刊论文
Zhao, JH; Habibulla, Y; Zhou, HJ; Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.
Statistical Mechanics of the Minimum Dominating Set Problem
Source PublicationJOURNAL OF STATISTICAL PHYSICS
Language英语
KeywordDominating Set Spin Glass Core Percolation Leaf Removal Network Coarse-graining Belief Propagation
AbstractThe minimum dominating set (MDS) problem has wide applications in network science and related fields. It aims at constructing a node set of smallest size such that any node of the network is either in this set or is adjacent to at least one node of this set. Although this optimization problem is generally very difficult, we show it can be exactly solved by a generalized leaf-removal (GLR) process if the network contains no core. We present a percolation theory to describe the GLR process on random networks, and solve a spin glass model by mean field method to estimate the MDS size. We also implement a message-passing algorithm and a local heuristic algorithm that combines GLR with greedy node-removal to obtain near-optimal solutions for single random networks. Our algorithms also perform well on real-world network instances.
2015
Volume159Issue:5Pages:1154-1174
Subject AreaPhysics
DOIhttp://dx.doi.org/10.1007/s10955-015-1220-2
Indexed BySCI
Funding OrganizationNational Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Basic Research Program of China [2013CB932804] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526] ; National Natural Science Foundation of China [11121403, 11225526]
Citation statistics
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/20987
CollectionSCI期刊论文
Corresponding AuthorZhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.
Recommended Citation
GB/T 7714
Zhao, JH,Habibulla, Y,Zhou, HJ,et al. Statistical Mechanics of the Minimum Dominating Set Problem[J]. JOURNAL OF STATISTICAL PHYSICS,2015,159(5):1154-1174.
APA Zhao, JH,Habibulla, Y,Zhou, HJ,&Zhou, HJ .(2015).Statistical Mechanics of the Minimum Dominating Set Problem.JOURNAL OF STATISTICAL PHYSICS,159(5),1154-1174.
MLA Zhao, JH,et al."Statistical Mechanics of the Minimum Dominating Set Problem".JOURNAL OF STATISTICAL PHYSICS 159.5(2015):1154-1174.
Files in This Item:
File Name/Size DocType Version Access License
Statistical Mechanic(847KB)期刊论文出版稿开放获取CC BY-NC-SAApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhao, JH]'s Articles
[Habibulla, Y]'s Articles
[Zhou, HJ]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhao, JH]'s Articles
[Habibulla, Y]'s Articles
[Zhou, HJ]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhao, JH]'s Articles
[Habibulla, Y]'s Articles
[Zhou, HJ]'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.