The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
文献类型：会议论文
| 作者 | Habibulla, Y; Zhao, JH; Zhou, HJ
|
| 出版日期 | 2015 |
| 会议日期 | JUL 03-05, 2015 |
| 会议地点 | Guilin, PEOPLES R CHINA |
| 关键词 | GRAPHS NETWORK |
| 卷号 | 9130 |
| DOI | 10.1007/978-3-319-19647-3_8 |
| 页码 | 78-88 |
| 英文摘要 | A minimum dominating set for a digraph (directed graph) is a smallest set of vertices such that each vertex either belongs to this set or has at least one parent vertex in this set. We solve this hard combinatorial optimization problem approximately by a local algorithm of generalized leaf removal and by a message-passing algorithm of belief propagation. These algorithms can construct near-optimal dominating sets or even exact minimum dominating sets for random digraphs and also for real-world digraph instances. We further develop a core percolation theory and a replica-symmetric spin glass theory for this problem. Our algorithmic and theoretical results may facilitate applications of dominating sets to various network problems involving directed interactions. |
| 会议录 | FRONTIERS IN ALGORITHMICS (FAW 2015)
 |
| 会议录出版者 | SPRINGER-VERLAG BERLIN |
| 会议录出版地 | BERLIN |
| 语种 | 英语 |
| URL标识 | 查看原文 |
| ISSN号 | 0302-9743 |
| WOS研究方向 | Computer Science ; Mathematics |
| ISBN号 | 978-3-319-19647-3; 978-3-319-19646-6 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/23584]  |
| 专题 | SCI会议论文 |
| 作者单位 | 1.[Habibulla, Yusupjan 2.Zhao, Jin-Hua 3.Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Habibulla, Y,Zhao, JH,Zhou, HJ. The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation[C]. 见:. Guilin, PEOPLES R CHINA. JUL 03-05, 2015. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。