计算机应用研究

作者：周晓清,叶安胜,张志强,

单位：1.电子科技大学计算机科学与工程学院,成都611731；2.成都大学信息科学与工程学院,成都610106；

关键词：NP难问题,精确算法,测量治之,连通支配集问题,

基金：国家重点研发计划资助项目(2016YFB0800605)；国家自然科学基金资助项目(61370071)；四川省教育厅科研项目重点项目(15ZA0354)；；

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

来源：2019年第9期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2019年第9期