无向图中连通支配集问题的精确算法

• 作者: 叶安胜 周晓清 张志强
• 来源期刊: 计算机应用研究
• 关键词: NP难问题 精确算法 测量治之 连通支配集问题
• 年，卷（期）: 2019,（9）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2569-2574
• 页数: 6页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2018.03.0154

摘要

图G=(V,E)的一个支配集D∈V是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连.连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G[S]是连通图.该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域.针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂度为O*(1.93n)的精确算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周晓清	电子科技大学计算机科学与工程学院	15	56	4.0	7.0
3	张志强	成都大学信息科学与工程学院	43	87	5.0	7.0
4	叶安胜	成都大学信息科学与工程学院	28	142	8.0	11.0