论文摘要
图G=(V,E)的一个支配集D?V是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G[S]是连通图。该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂度为O*(1. 93n)的精确算法。
论文目录
文章来源
类型: 期刊论文
作者: 周晓清,叶安胜,张志强
关键词: 难问题,精确算法,测量治之,连通支配集问题
来源: 计算机应用研究 2019年09期
年度: 2019
分类: 信息科技,基础科学
专业: 数学
单位: 电子科技大学计算机科学与工程学院,成都大学信息科学与工程学院
基金: 国家重点研发计划资助项目(2016YFB0800605),国家自然科学基金资助项目(61370071),四川省教育厅科研项目重点项目(15ZA0354)
分类号: O157.5
DOI: 10.19734/j.issn.1001-3695.2018.03.0154
页码: 2569-2574
总页数: 6
文件大小: 277K
下载量: 99
相关论文文献
- [1].基于连通支配集的无线传感器网络拓扑控制算法仿真研究[J]. 仪表技术与传感器 2016(09)
- [2].有向图的广义支配集及其求解算法[J]. 山东大学学报(理学版) 2013(08)
- [3].完全p-支配集的参数算法[J]. 计算机学报 2013(09)
- [4].无线网络中一种简单的弱连通支配集构造策略[J]. 计算机工程与应用 2011(20)
- [5].一种高效的最小连通支配集贪心算法[J]. 计算机工程与应用 2012(13)
- [6].求解最小连通r-跳k-支配集的启发式算法[J]. 计算机工程 2012(21)
- [7].最小连通支配集问题的化简算法[J]. 计算机工程 2011(10)
- [8].连通支配集一种集中式近似算法[J]. 电脑知识与技术 2009(10)
- [9].连通支配集算法及其改进[J]. 现代电子技术 2009(16)
- [10].无线网络连通支配集分布式构造[J]. 曲阜师范大学学报(自然科学版) 2019(03)
- [11].最小连通支配集问题的分解算法[J]. 沈阳师范大学学报(自然科学版) 2017(04)
- [12].一种参考能量的最小连通支配集近似算法[J]. 传感器与微系统 2015(01)
- [13].基于域的分布式最小连通支配集的启发式算法[J]. 计算机系统应用 2011(02)
- [14].求解圆盘图中最小连通支配集的近似算法[J]. 计算机应用 2011(07)
- [15].两跳支配集的高效近似算法[J]. 西北师范大学学报(自然科学版) 2011(05)
- [16].有向图连通支配集求解算法[J]. 计算机工程与应用 2010(21)
- [17].高效的分布式最小连通支配集近似算法[J]. 计算机工程 2008(23)
- [18].一种求解最小连通支配集的高效近似算法[J]. 小型微型计算机系统 2008(05)
- [19].一种基于信任评估的连通支配集生成算法[J]. 西安邮电大学学报 2019(01)
- [20].无线传感器网络中2-连通k-支配的容错连通支配集构造[J]. 控制与决策 2013(05)
- [21].基于区域划分的连通支配集协议[J]. 计算机工程与设计 2012(04)
- [22].无线传感器网络中的连通支配集求解算法[J]. 微计算机信息 2010(01)
- [23].2-连通2-支配集的集中式构造[J]. 计算机工程与应用 2009(15)
- [24].完全支配集的规约算法[J]. 计算机科学 2017(S2)
- [25].无线传感器网络中基于有向图的强连通支配集的构造[J]. 南昌航空大学学报(自然科学版) 2016(02)
- [26].能量均衡的最小2-连通2-支配集的分布式算法[J]. 计算机系统应用 2014(08)
- [27].无线传感器网络中能量有效的最小连通支配集算法[J]. 西安石油大学学报(自然科学版) 2012(05)
- [28].基于连通支配集的虚拟骨干网构造算法[J]. 计算机工程 2011(01)
- [29].基于串行最大独立集的连通支配集构造及分析[J]. 华中科技大学学报(自然科学版) 2011(03)
- [30].基于学习自动机的最小连通支配集算法[J]. 计算机工程 2011(10)