Statistical Mechanics of the Minimum Dominating Set Problem

CORC > 理论物理研究所 > 中国科学院理论物理研究所 > 理论物理所科研产出 > 理论物理所1978-2010年知识产出

	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.