Statistical Mechanics of the Minimum Dominating Set Problem
文献类型：期刊论文
| 作者 | Zhao, JH; Habibulla, Y; Zhou, HJ
|
| 刊名 | JOURNAL OF STATISTICAL PHYSICS
 |
| 出版日期 | 2015 |
| 卷号 | 159期号:5页码:1154-1174 |
| 关键词 | Dominating set Spin glass Core percolation Leaf removal Network coarse-graining Belief propagation |
| 通讯作者 | 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. |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| 类目[WOS] | Physics, Mathematical |
| 关键词[WOS] | SCALE-FREE NETWORKS ; COMPLEX NETWORKS ; CONTROLLABILITY ; PERCOLATION ; TRANSITION ; GRAPHS |
| 收录类别 | SCI |
| 语种 | 英语 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/20987]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 推荐引用方式 GB/T 7714 | Zhao, JH,Habibulla, Y,Zhou, HJ. 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.(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. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。