| 无向图中连通支配集问题的精确算法 |
| |
| 引用本文： | 周晓清,叶安胜,张志强. 无向图中连通支配集问题的精确算法[J]. 计算机应用研究, 2019, 36(9) |
| |
| 作者姓名： | 周晓清 叶安胜 张志强 |
| |
| 作者单位： | 电子科技大学计算机科学与工程学院,成都611731;成都大学信息科学与工程学院,成都610106;成都大学信息科学与工程学院,成都,610106 |
| |
| 基金项目： | 国家重点研发计划资助项目(2016YFB0800605);国家自然科学基金资助项目(61370071);四川省教育厅科研项目重点项目(15ZA0354) |
| |
| 摘 要： | 图◢G=（V,E）的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G［S］是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△（1.93n△）的精确◣算法。
|
| 关 键 词： | NP难问题 精确算法 测量治之 连通支配集问题 |
| 收稿时间： | 2018-03-08 |
| 修稿时间： | 2018-04-23 |
Exact algorithms for connected dominating set in undirected graphs |
| |
| ZHOU Xiao-Qing,YE An-Sheng and ZHANG Zhi-Qiang. Exact algorithms for connected dominating set in undirected graphs[J]. Application Research of Computers, 2019, 36(9) |
| |
| Authors: | ZHOU Xiao-Qing YE An-Sheng ZHANG Zhi-Qiang |
| |
| Affiliation: | School of Computer Science and Engineering,University of Electronic Science and Technology of China;College of Information Science and Engineering,Chengdu University,, |
| |
| Abstract: | |
| |
| Keywords: | NP-hard problem exact algorithms measure-and-conquer connected dominating set problem |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
|
