ITP OpenIR  > 理论物理所SCI论文
Statistical Mechanics of the Minimum Dominating Set Problem
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.
2015
发表期刊JOURNAL OF STATISTICAL PHYSICS
卷号159期号:5页码:1154-1174
文章类型Article
摘要The 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.
关键词Dominating Set Spin Glass Core Percolation Leaf Removal Network Coarse-graining Belief Propagation
学科领域Physics
资助者National 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] ; National 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]
DOIhttp://dx.doi.org/10.1007/s10955-015-1220-2
关键词[WOS]SCALE-FREE NETWORKS ; COMPLEX NETWORKS ; CONTROLLABILITY ; PERCOLATION ; TRANSITION ; GRAPHS
收录类别SCI
语种英语
资助者National 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] ; National 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]
WOS类目Physics, Mathematical
引用统计
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/20987
专题理论物理所SCI论文
通讯作者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.
推荐引用方式
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.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Statistical Mechanic(847KB)期刊论文出版稿开放获取CC BY-NC-SA请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Zhao, JH]的文章
[Habibulla, Y]的文章
[Zhou, HJ]的文章
百度学术
百度学术中相似的文章
[Zhao, JH]的文章
[Habibulla, Y]的文章
[Zhou, HJ]的文章
必应学术
必应学术中相似的文章
[Zhao, JH]的文章
[Habibulla, Y]的文章
[Zhou, HJ]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

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