《计算机应用研究》|Application Research of Computers

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

Exact algorithm for connected dominating set in undirected graphs

免费全文下载 (已被下载 次)  
获取PDF全文
作者 周晓清,叶安胜,张志强
机构 1.电子科技大学 计算机科学与工程学院,成都 611731;2.成都大学 信息科学与工程学院,成都 610106
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)09-002-2569-06
DOI 10.19734/j.issn.1001-3695.2018.03.0154
摘要 图<i>G=(V,E)的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G[S]是连通图。</i>该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂<i>度为O<sup>*</sup>(1.93<sup>n</sup>)的精确</i>算法。
关键词 NP难问题; 精确算法; 测量治之; 连通支配集问题
基金项目 国家重点研发计划资助项目(2016YFB0800605)
国家自然科学基金资助项目(61370071)
四川省教育厅科研项目重点项目(15ZA0354)
本文URL http://www.arocmag.com/article/01-2019-09-002.html
英文标题 Exact algorithm for connected dominating set in undirected graphs
作者英文名 Zhou Xiaoqing, Ye Ansheng, Zhang Zhiqiang
机构英文名 1.School of Computer Science & Engineering,University of Electronic Science & Technology of China,Chengdu 611731,China;2.College of Information Science & Engineering,Chengdu University,Chengdu 610106,China
英文摘要 A dominating set <i>DV </i>of a graph <i>G=(V, E</i>) was a subset of vertices, such that every vertex of <i>G</i> was either in <i>D</i>, or adjacent to at least one vertex in <i>D</i>. The connected dominating set problem asks to find a dominating set <i>S</i> with minimum number of vertices and the induced subgraph <i>G[S]</i> of <i>S</i> was connected. The connected dominating set problem was a classical NP-hard problem, which could be applied to connected facility location, Ad-hoc networks and many other areas. For the connected dominating set problem in undirected graphs, this paper carefully analyzed the structural properties, explored a number of effective reduction rules as well as branching rules and provided a branch-and-search algorithm. A measure-and-conquer method is also introduced to analyze the running time bound. Finally, an exact algorithm with a running time complexity of <i>O<sup>*</sup>(1.93<sup>n</sup>) </i> is obtained.
英文关键词 NP-hard problem; exact algorithms; measure-and-conquer; connected dominating set problem
参考文献 查看稿件参考文献
 
收稿日期 2018/3/8
修回日期 2018/4/23
页码 2569-2574
中图分类号 TP301.6
文献标志码 A