Current Location:home > Detailed Browse

Article Detail

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

Abstracts

图G=(V,E)的一个支配集D?V是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G[S]是连通图。该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂度为O*(1.93^n)的精确算法。
Download Comment From cooperative journals:《计算机应用研究》 Hits:897 Downloads:519
Journal:计算机应用研究
Recommended references: 周晓清,叶安胜,张志强.(2018).无向图中连通支配集问题的精确算法.计算机应用研究.[ChinaXiv:201805.00470] (Click&Copy)
Version History
[V1] 2018-05-24 21:08:13 chinaXiv:201805.00470V1 Download
Related Paper

Download

Current Browse

Cross Subject Browse

  • - NO